Any comparison sort needs on the order of n log n comparisons in the worst case, so the algorithms in this section are asymptotically optimal. They differ in the constants, in worst-case guarantees, in stability, in memory use and in how well they exploit existing order in the input.
O(n log n) comparison sorts: mergesort, quicksort, heapsort, Timsort, tree sort and Cubesort.
Cubesort is a parallel comparison sort that maintains a cube-shaped index of sorted runs and merges them adaptively. It is rarely seen in everyday code; the…
Heapsort is a comparison sort that uses a binary heap to repeatedly extract the maximum. It runs in O(n log n) time, in place, with O(1) extra space — the…
Mergesort is a divide-and-conquer comparison sort that recursively splits the array in half, sorts each half, then merges them. It guarantees O(n log n) on…
Quicksort is a divide-and-conquer comparison sort that picks a pivot, partitions the array around it, and recursively sorts the partitions. In practice it is…
Timsort is a hybrid stable sort derived from mergesort and insertion sort. It is the algorithm behind Python's built-in and , and Java's on object arr
Tree sort inserts every element into a binary search tree, then performs an in-order traversal to read them out sorted. Performance hinges entirely on the…
Mergesort and quicksort split the input and recurse: mergesort does the work when merging, quicksort when partitioning. Heapsort and tree sort insert elements into a data structure that maintains order and then extract them. Timsort and Cubesort detect runs that are already sorted and merge them, so they approach linear time on partially ordered real-world data. Production libraries combine these ideas: Python and Java (for objects) use Timsort; C++ std::sort uses introsort, a quicksort that falls back to heapsort.
| Algorithm | Average | Worst | Extra space | Stable |
|---|---|---|---|---|
| Mergesort | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n^2) | O(log n) | No |
| Heapsort | O(n log n) | O(n log n) | O(1) | No |
| Timsort | O(n log n) | O(n log n) | O(n) | Yes |
| Tree sort | O(n log n) | O(n^2) unbalanced, O(n log n) balanced | O(n) | Yes with care |
| Cubesort | O(n log n) | O(n log n) | O(n) | Yes |
Use the built-in sort (Timsort in Python) unless you have a reason not to. Choose quicksort-based sorts for in-memory primitives where speed matters and stability does not, heapsort when memory is fixed and worst-case bounds matter, and mergesort for linked lists and external sorting of data larger than memory.