12.6. Sorting: Faster Sorts¶
12.6.1. Faster Sorts¶
12.6.1.1. Shellsort¶
12.6.1.2. Shellsort (2)¶
12.6.1.3. Mergesort¶
12.6.1.4. .¶
.
12.6.1.5. Mergesort cost¶
Mergesort cost:
Mergesort is also good for sorting linked lists.
Mergesort requires twice the space.
12.6.1.6. Quicksort¶
12.6.1.7. Quicksort Partition¶
12.6.1.8. Quicksort Partition Cost¶
12.6.1.9. Quicksort Summary¶
12.6.1.10. Quicksort Worst Case¶
12.6.1.11. .¶
.
12.6.1.12. Quicksort Best Case¶
12.6.1.13. .¶
.
12.6.1.14. Quicksort Average Case¶
12.6.1.15. Optimizations for Quicksort¶
Better Pivot
Inline instead of function calls
Eliminate recursion
- Better algorithm for small sublists: Insertion sort
Best: Don’t sort small lists at all, do a final Insertion Sort to clean up.
