Quick sort is another divide-and-conquer sorting algorithm, and on average it has the exact same O(n log n) time complexity as merge sort — yet in practice, it's often the faster choice, which is why it's the algorithm behind many real-world sort implementations in C and C++ standard libraries. The reason comes down to how it uses memory, not just how it counts comparisons.

The Partition Idea

Quick sort picks one element from the array — called the pivot — and rearranges the rest of the array so that everything smaller than the pivot ends up to its left, and everything larger ends up to its right. This rearrangement step is called partitioning. Once partitioned, the pivot is in its final sorted position, and quick sort recursively repeats the same process on the left and right sub-arrays.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)


print(quick_sort([38, 27, 43, 3, 9, 82, 10]))

Output:

[3, 9, 10, 27, 38, 43, 82]

This version is easy to read because it builds new lists with Python's list comprehensions, but it isn't the in-place version used in practice — see the quick sort program example for the classic Lomuto/Hoare partition scheme that sorts the array in place.

Average O(n log n), Worst-Case O(n²)

Quick sort's performance hinges entirely on how balanced the partitions turn out to be. If the pivot consistently splits the array roughly in half, you get the same O(n log n) behavior as merge sort — log n levels of recursion, O(n) work partitioning at each level. But if the pivot is consistently the smallest or largest element (which happens, for example, if you always pick the first element as pivot on an already-sorted array), each partition only shrinks the problem by one element, and the recursion degrades to O(n²) — essentially behaving like selection sort. Picking the pivot randomly, or using the "median of three" heuristic, makes this worst case extremely unlikely in practice.

Why Quick Sort Often Wins in Practice

Despite sharing the same average-case Big O as merge sort, quick sort typically runs faster on real hardware for two reasons. First, the in-place version needs only O(log n) extra space (for the recursion stack) rather than merge sort's O(n) for auxiliary arrays — less memory allocation means less overhead. Second, quick sort has better cache locality: because it works within contiguous sections of the same array rather than copying data into new lists at every step, modern CPUs can keep more of the relevant data in fast cache memory, which matters a lot more for real-world speed than Big O notation alone captures.

The tradeoff is predictability — merge sort's guaranteed O(n log n) makes it the safer choice when worst-case performance genuinely matters (e.g. a library sort that must handle adversarial or already-sorted input reliably), while quick sort is usually the faster everyday choice.