Time Complexity of All Sorting Algorithms (Comparison Table)

No sorting algorithm that works by comparing elements can do better than O(n log n) time in the average case or the worst case. Merge sort and heap sort reach O(n log n) in every case. Quicksort reaches it on average but drops to O(n²) on a bad sequence of pivots. Counting sort, radix sort, and bucket sort do not compare elements at all. They sort integers in a bounded range in O(n + k) time, where k is the size of that range.

The reason for the O(n log n) limit is counting. A list of n items has n factorial possible orders. Each comparison rules out at most half of the orders that remain, so at least log2 of n factorial comparisons are needed. That quantity grows as n log n. An algorithm that never compares elements is not bound by that argument.

Sorting Algorithm Complexity Table

Two terms are used in the table. A sort is stable if elements with equal keys keep the order they had in the input. Extra space is the memory needed beyond the input array, and a sort is in-place if that extra space is O(1) or O(log n).

In the table, n is the number of elements and d is the number of digits in the longest key. The letter k is the range of key values, or the number of buckets for bucket sort. Bubble sort reaches O(n) only in the version that stops early when a pass makes no swaps. Shell sort's average depends on the gap sequence, and the O(n²) worst case is for the original sequence that halves the gap each round. Quicksort's O(log n) extra space is the recursion stack, and it is conventionally counted as in-place.

Notes on the Table

Why quicksort is used despite its O(n²) worst case. The worst case appears only when the pivot is repeatedly the smallest or largest element. A random pivot or a median-of-three pivot makes that sequence extremely unlikely. Quicksort works on one contiguous section of the array at a time, so it uses the processor cache well and does fewer memory writes than merge sort. On random data it is usually the fastest comparison sort in practice, which is why Java's sort for primitive arrays is a quicksort variant.

Why merge sort is chosen when stability matters. Stability matters whenever you sort by one field after sorting by another. Sorting orders by date and then by customer keeps the date order inside each customer only if the second sort is stable. Merge sort is stable and guarantees O(n log n) in the worst case, at the cost of O(n) extra memory. It also suits linked lists and data too large to fit in memory, because it reads and writes in sequence.

Why Timsort is the default in Python and Java. Timsort finds runs, which are stretches of the input that are already in order, and merges them. It therefore finishes in O(n) time on sorted or nearly sorted input while keeping the O(n log n) worst case and the stability of merge sort. Real data is often partly sorted, and objects usually need stability. Python's built-in sort and Java's sort for object arrays both use it. Java sorts primitive arrays with quicksort instead, because stability has no meaning for plain numbers.