Sorting Algorithms Compared: Quicksort, Mergesort, Heapsort, and When to Use Each

Every sorting algorithm makes trade-offs between time complexity, space usage, and stability. This guide breaks down the most important algorithms at a glance, then digs into the mechanics so you understand why Python and Java do not use the same sort as a C++ STL implementation.

At a Glance: Complexity and Properties

Before diving into the mechanics, here is a side-by-side comparison. Stable means equal elements preserve their original relative order after sorting, which matters when you sort by multiple keys in sequence.

Quicksort: Fast in Practice, Dangerous Without Care

Quicksort partitions the array around a pivot element, placing all smaller values to the left and all larger values to the right, then recursively sorts each partition. The pivot choice is critical: a badly chosen pivot (always the minimum or maximum) produces the O(n²) worst case. Random pivot selection or the median-of-three heuristic keeps average performance reliably O(n log n).

The Lomuto partition scheme is straightforward to implement. It moves a boundary index i forward whenever it finds an element smaller than the pivot:

def quicksort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)
        quicksort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot = arr[high]       # choose last element as pivot
    i = low - 1             # boundary of "less than pivot" region
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Usage:
data = [8, 3, 1, 7, 5, 2]
quicksort(data, 0, len(data) - 1)
# data is now [1, 2, 3, 5, 7, 8]

Quicksort is not stable and is not ideal for linked lists (it relies on random access). Its biggest advantage is excellent cache behaviour on arrays: partition scans are sequential reads with very few cache misses. This is why C's qsort and C++ STL std::sort use introsort, a hybrid that starts with quicksort and switches to heapsort when recursion depth becomes excessive.

Mergesort: Guaranteed O(n log n) and Stable

Mergesort is a divide-and-conquer algorithm. It splits the array in half, recursively sorts each half, then merges the two sorted halves back together. The merge step scans both halves in order, always picking the smaller front element. Because the merge preserves the relative order of equal elements, mergesort is stable.

The cost is O(n) auxiliary space for the merge buffer. That makes mergesort the standard choice for sorting linked lists (where random access is O(n)) and for external sorting, where data does not fit in memory and must be merged from disk chunks. Java uses a variant of mergesort called Timsort for its Arrays.sort when sorting objects, precisely because stability matters for higher-level sort keys.

Heapsort: In-Place but Cache-Hostile

Heapsort builds a max-heap from the input array in O(n) time, then repeatedly extracts the maximum element (swapping it to the end) and re-heapifying the remaining portion. The result is a sorted array, all in-place with O(1) extra space.

Despite its excellent theoretical profile, heapsort is rarely the fastest in practice. Heap operations jump around the array following parent-child index arithmetic, producing scattered memory accesses that thrash the CPU cache. Quicksort, with its sequential partition scans, almost always beats heapsort in wall-clock time on modern hardware even though both are O(n log n). Understanding this gap is a good exercise in why time complexity does not tell the whole story.

Timsort: What Python and Java Actually Use

Python's built-in sorted() and list.sort() use Timsort, invented by Tim Peters in 2002. Java uses it for object arrays since Java 7. Timsort is a hybrid of mergesort and insertion sort, and it is engineered to exploit structure that already exists in real-world data.

The algorithm scans the input for natural runs — sequences that are already sorted (ascending or descending). Runs shorter than a minimum size (usually 32 to 64 elements) are extended using insertion sort, which is extremely fast on nearly-sorted small arrays. The runs are then merged using a mergesort-style merge. On already-sorted or nearly-sorted input, Timsort achieves O(n) time. In the worst case it falls back to O(n log n).

Insertion Sort for Small Arrays

Insertion sort has O(n²) average complexity, which makes it look useless. In practice it is the fastest choice for arrays with fewer than roughly 10 to 20 elements. Its inner loop is a simple backwards scan with a single comparison and shift per step, and the constant factor is tiny. This is why Timsort uses it internally, and why most production sort implementations switch to insertion sort below a threshold rather than recursing all the way down to single-element base cases.

For a deeper look at how complexity classes relate to real performance, see our article on big-O notation.