Algorithms · topic
Insertion, selection and bubble sort with exact comparisons and swaps, inversions, merge sort, quicksort with Lomuto and Hoare partitions and pivot cases, heap sort, counting, radix and bucket sort, the n log n comparison lower bound and a master comparison table.
Sorting rearranges n records so that their keys are in non-decreasing order. Bubble sort, selection sort and insertion sort are the three simple quadratic methods. Their worst-case quadratic cost is slower than merge sort or heapsort on large inputs, but they are short and in place.
Merge sort is the standard example of divide and conquer. It splits the array into two halves, sorts each half recursively, and merges the two sorted halves in linear time. Its worst-case running time is Θ(n lg n), which matches the lower bound for comparison sorting, and it is stable.
Quicksort sorts by divide and conquer, but puts the work in the divide step. It chooses a pivot, partitions the array so that smaller elements come before larger ones, and then sorts the two parts recursively; no combine step is needed.
Heapsort sorts an array by first arranging it into a max-heap and then repeatedly moving the maximum to the end. It is the only standard comparison sort that is both in place (O(1) auxiliary space) and guaranteed O(n lg n) in the worst case.
Every comparison sort needs Ω(n lg n) comparisons in the worst case (see Comparison of Sorting Algorithms). The three algorithms in this note beat that bound because they are not comparison sorts: they use the keys as array indices or split them into digits.
Brings the sorting algorithms together: the lower bound that no comparison sort can beat, exact comparison counts for related problems, and a comparison of all standard sorts on time, space, stability and adaptivity.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
