Quick Sort, Merge Sort and Heap Sort: How O(n log n) Sorting Works and When Each Wins

Introduction

Advanced sorting achieves O(n log n) using divide and conquer. These are the sorting algorithms used in practice and coding interviews.

The O(n log n) figure is not arbitrary. Any sort that works only by comparing pairs of elements must be able to distinguish all n! possible orderings, and each comparison gives one bit of information, so it needs at least log₂(n!) ≈ n log₂ n comparisons in the worst case. Quick sort, merge sort and heap sort all reach that bound, which is why none of them is asymptotically “better”. The differences that decide between them are the constants, the worst case, memory use, and whether equal elements keep their order. Those differences are what this article focuses on, because they are also what interview questions about sorting are really probing.

---

Quick Sort

Algorithm

Partition around pivot:

[5, 2, 8, 1, 9, 3]
pivot = 5
[2, 1, 3] 5 [8, 9]
   ↓           ↓
[1, 2, 3]   [8, 9]

Python Implementation

Below is a method that divides into three chunks left / equal / right based on pivot, then recursively sorts left and right. Creates new lists, making implementation readable and good for following divide-and-conquer flow.

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)
# Test
arr = [5, 2, 8, 1, 9, 3]
print(quick_sort(arr))  # [1, 2, 3, 5, 8, 9]

Step-by-Step Trace (the pivot is the element at index len // 2):

[5, 2, 8, 1, 9, 3]
pivot=arr[3]=1
left=[], middle=[1], right=[5,2,8,9,3]
quick_sort([5,2,8,9,3]):
  pivot=arr[2]=8
  left=[5,2,3], middle=[8], right=[9]
  
  quick_sort([5,2,3]):
    pivot=arr[1]=2
    left=[], middle=[2], right=[5,3]
    
    quick_sort([5,3]):
      pivot=arr[1]=3
      left=[], middle=[3], right=[5]
      return [3,5]
    
    return [2,3,5]
  
  quick_sort([9]):
    return [9]
  return [2,3,5,8,9]
Final: [1,2,3,5,8,9]

The trace also shows quick sort’s weakness in miniature: the first pivot is the minimum, so one side is empty and the other has n−1 elements. When that keeps happening, the recursion becomes n levels deep and the total work is n + (n−1) + … = O(n²). A good pivot splits the array roughly in half, giving log n levels of O(n) work each.

This three-list version is the easiest to reason about, and the middle list handles duplicates well: an array of identical values finishes in one step, whereas a naive two-way partition degrades to O(n²) on it. The cost is memory. Every level builds new lists, so it uses O(n) extra space per level and allocates heavily, and each element is compared against the pivot three times. It is a teaching and interview implementation; real implementations partition in place.

In-Place Implementation

def quick_sort_inplace(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort_inplace(arr, low, pi - 1)
        quick_sort_inplace(arr, pi + 1, high)
def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    
    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
arr = [5, 2, 8, 1, 9, 3]
quick_sort_inplace(arr, 0, len(arr) - 1)
print(arr)  # [1, 2, 3, 5, 8, 9]

Partition Trace:

arr = [5, 2, 8, 1, 9, 3], pivot=3
i=-1, j=0: arr[0]=5 (>= 3, skip)
i=-1, j=1: arr[1]=2 (< 3, i++, swap)
  i=0, swap arr[0] and arr[1]: [2, 5, 8, 1, 9, 3]
i=0, j=2: arr[2]=8 (>= 3, skip)
i=0, j=3: arr[3]=1 (< 3, i++, swap)
  i=1, swap arr[1] and arr[3]: [2, 1, 8, 5, 9, 3]
i=1, j=4: arr[4]=9 (>= 3, skip)
Final swap arr[i+1] and arr[high]:
[2, 1, 3, 5, 9, 8]
return i+1=2

This is the Lomuto partition scheme. The invariant is that arr[low..i] holds elements smaller than the pivot and arr[i+1..j-1] holds elements greater than or equal to it; each step either extends the first region with a swap or leaves the element in the second. After the loop, swapping the pivot into position i + 1 puts it exactly where it belongs in the sorted output, and it never moves again. Lomuto is easy to get right, which is why textbooks use it. Hoare’s original scheme, with two indices moving toward each other, does about three times fewer swaps on average and handles many duplicates better, but its boundary conditions are notoriously easy to get wrong.

Choosing arr[high] as the pivot is what makes already sorted input the worst case for this version: the pivot is always the maximum, every partition peels off one element, and on a sorted list of a few thousand elements Python raises RecursionError: maximum recursion depth exceeded long before the O(n²) time becomes noticeable. Choosing a random index (and swapping it to high first) or the median of the first, middle and last elements avoids that. Recursing into the smaller side first and looping on the larger one bounds the stack depth at O(log n) even in the worst case.

Time Complexity

• Best: O(n log n)
• Average: O(n log n)
• Worst: O(n²) (with a fixed first/last pivot, e.g. on already sorted input)
• Space: O(log n) recursion stack on average for the in-place version, O(n) in the worst case
• Stable: No

---

Merge Sort

Algorithm

Divide → Sort → Merge:

[5, 2, 8, 1]
   ↓ Divide
[5, 2] [8, 1]
   ↓ Divide
[5] [2] [8] [1]
   ↓ Merge
[2, 5] [1, 8]
   ↓ Merge
[1, 2, 5, 8]

Python Implementation

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)
def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result
# Test
arr = [5, 2, 8, 1, 9, 3]
print(merge_sort(arr))  # [1, 2, 3, 5, 8, 9]

Merge Process:

Merge [2, 5] and [1, 8]:
i=0, j=0: left[0]=2, right[0]=1
  1 < 2 → result=[1], j++
i=0, j=1: left[0]=2, right[1]=8
  2 < 8 → result=[1,2], i++
i=1, j=1: left[1]=5, right[1]=8
  5 < 8 → result=[1,2,5], i++
i=2 (end): result.extend([8])
  result=[1,2,5,8]

The <= in if left[i] <= right[j] is what makes merge sort stable: when two elements are equal, the one from the left half, which came first in the input, is taken first. Changing it to < still sorts correctly but loses stability, a one-character bug that tests with plain integers never catch.

Merge sort’s guarantee comes from its structure rather than from luck: the array is always split exactly in half, so there are always about log₂ n levels, and each level merges n elements in total. The price is the O(n) buffer for merging. This implementation also slices (arr[:mid]), which copies, so it allocates more than necessary; an index-based version with one shared buffer is what production code uses. Merge sort’s sequential access pattern is also why it is the basis of external sorting: when data does not fit in memory, you sort chunks, write them to disk, and merge the sorted files, reading each one front to back. It is likewise the natural sort for linked lists, where merging needs no extra buffer at all.

Time Complexity

• Best: O(n log n)
• Average: O(n log n)
• Worst: O(n log n) (always consistent!)
• Space: O(n)
• Stable: Yes

---

Heap Sort

Algorithm

Build max heap → Extract one by one:

def heap_sort(arr):
    import heapq
    
    # Use min heap
    heap = []
    for num in arr:
        heapq.heappush(heap, num)
    
    result = []
    while heap:
        result.append(heapq.heappop(heap))
    
    return result
# Test
arr = [5, 2, 8, 1, 9, 3]
print(heap_sort(arr))  # [1, 2, 3, 5, 8, 9]

This version shows the idea with Python’s heapq (a binary min-heap stored in a list): push everything, then pop the smallest repeatedly. Each push and pop costs O(log n), so the total is O(n log n), but it uses a second list and is not what “heap sort” means in textbooks. Replacing the push loop with heap = arr[:] followed by heapq.heapify(heap) builds the heap in O(n) instead of O(n log n), which is the same trick the in-place version uses.

In-Place Heap Sort

def heap_sort_inplace(arr):
    """
    In-place heap sort using max heap
    """
    n = len(arr)
    
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    
    return arr
def heapify(arr, n, i):
    """
    Heapify subtree rooted at index i
    """
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
# Test
arr = [5, 2, 8, 1, 9, 3]
print(heap_sort_inplace(arr))  # [1, 2, 3, 5, 8, 9]

The array is treated as a complete binary tree: the children of index i are 2i + 1 and 2i + 2. The first loop turns the whole array into a max-heap, starting from the last node that has children (n // 2 - 1) and sifting each one down. Although it calls heapify n/2 times, this phase is O(n), because most nodes are near the bottom and sift down only a level or two. The second loop swaps the maximum (the root) to the end of the array, shrinks the heap by one, and restores the heap property from the root, which is O(log n) per step. Using a max-heap is what lets the sorted output grow from the back of the same array.

Heap sort is the only one of the three with both a guaranteed O(n log n) and O(1) extra memory, which is exactly why introsort uses it as the fallback when quick sort’s recursion gets too deep. It is rarely the primary sort, though, because sifting jumps between index i and 2i + 1, which is far apart in memory for large arrays and therefore cache-unfriendly; on large inputs it is typically slower than a well-implemented quick sort. (The recursive heapify here uses O(log n) stack; a while loop version is truly O(1).)

Time Complexity

• Best: O(n log n)
• Average: O(n log n)
• Worst: O(n log n)
• Space: O(1) (in-place possible)
• Stable: No

---

Sorting Comparison

Algorithm	Average	Worst	Space	Stable	Feature
Quick	O(n log n)	O(n²)	O(log n)	No	Usually fastest in practice
Merge	O(n log n)	O(n log n)	O(n)	Yes	Consistent
Heap	O(n log n)	O(n log n)	O(1)	No	In-place

When to Use Each

# Quick Sort
# - Average case performance critical
# - In-place sorting needed
# - Unstable is acceptable
# Merge Sort
# - Stable sorting required
# - Worst case O(n log n) guaranteed
# - Extra space available
# Heap Sort
# - In-place + O(n log n) guaranteed
# - Don't need stability
# - Priority queue operations

Why quick sort usually wins despite the worse worst case: its inner loop compares against one pivot held in a register and walks memory sequentially, so it makes good use of CPU caches, and it needs no merge buffer. Merge sort does fewer comparisons on average, which is why it is preferred when comparisons are expensive (comparing long strings or calling a Python key function), and it is the one to choose when stability matters. That trade-off explains the standard library choices: Python sorts arbitrary objects, where comparisons dominate and stability is part of the language contract, so it uses a merge-based Timsort; C++ std::sort sorts values where moves are cheap and makes no stability promise, so it uses introsort.

---

Practical Problems

Problem 1: Kth Largest Element

import heapq
def kth_largest(arr, k):
    """
    Kth largest number (O(n log k))
    """
    heap = []
    
    for num in arr:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    
    return heap[0]
# Test
arr = [3, 2, 1, 5, 6, 4]
print(kth_largest(arr, 2))  # 5

The trick is to keep a min-heap of size k: it always holds the k largest values seen so far, and its root is the smallest of them, which is the answer once all elements are processed. Each element costs O(log k), so this is O(n log k) time and O(k) memory, and it works on a stream you cannot hold in memory. heapq.nlargest(k, arr)[-1] does the same in one line. Sorting the whole array and indexing (sorted(arr)[-k]) is O(n log n) and perfectly acceptable when n is small, which is worth saying out loud in an interview before optimizing. Using Quick Select (O(n) average):

def quick_select(arr, k):
    """
    Find kth largest using quick select
    Average O(n), worst O(n²)
    """
    if len(arr) == 1:
        return arr[0]
    
    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]
    
    if k <= len(left):
        return quick_select(left, k)
    elif k <= len(left) + len(middle):
        return middle[0]
    else:
        return quick_select(right, k - len(left) - len(middle))
# Test
arr = [3, 2, 1, 5, 6, 4]
print(quick_select(arr, 2))  # 5

Quick select partitions like quick sort but recurses into one side only, the side that contains the k-th position. With balanced pivots the work is n + n/2 + n/4 + … ≈ 2n, so it is O(n) on average, and the same O(n²) worst case as quick sort applies with bad pivots. Here left holds the values greater than the pivot because we want the k-th largest. The middle[0] branch is what handles duplicates: for [5, 5, 5] and k = 2, the answer is found without recursing forever. For guaranteed O(n), the median-of-medians pivot exists, but its constant factor is large enough that it is mostly of theoretical interest.

Problem 2: Merge Sorted Arrays

def merge_sorted_arrays(arr1, arr2):
    """
    Merge two sorted arrays (O(n+m))
    """
    result = []
    i = j = 0
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1
    
    result.extend(arr1[i:])
    result.extend(arr2[j:])
    return result
# Test
arr1 = [1, 3, 5]
arr2 = [2, 4, 6]
print(merge_sorted_arrays(arr1, arr2))
# [1, 2, 3, 4, 5, 6]

This is the merge step of merge sort on its own, O(n + m). Note that it uses < rather than <=, so on ties it takes from arr2 first; that does not matter for plain numbers, but if the arrays hold records and stability matters, use <=. LeetCode 88 asks for the same merge in place into arr1, which has extra space at the end; the standard solution fills from the back, comparing the largest remaining elements, so nothing is overwritten before it is read. For k sorted lists, heapq.merge(*lists) merges lazily in O(N log k).

---

Bugs that show up when you write these sorts yourself

Pivot choice and the missing base case

# ❌ Wrong: first/last-element pivot on already sorted input
arr = [1, 2, 3, 4, 5]
quick_sort_inplace(arr, 0, len(arr) - 1)  # pivot = arr[high]: O(n²), deep recursion
# (the middle-pivot quick_sort above is fine on sorted input)
# ✅ Better: random or median-of-three pivot, or the built-in
arr.sort()  # Timsort detects the sorted run: O(n)
# ❌ Wrong: Forgot base case
def quick_sort(arr):
    pivot = arr[0]  # Error if arr is empty!
    # ...
# ✅ Correct: Check base case
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    # ...

In Python the sorted-input case with a last-element pivot does not just get slow: the recursion depth grows to n, and past roughly 1,000 elements it raises RecursionError: maximum recursion depth exceeded under the default recursion limit. Raising the limit with sys.setrecursionlimit only hides the O(n²) behaviour. The usual fix is a random pivot plus recursing into the smaller partition and looping on the larger one, which bounds the stack depth at O(log n).

Getting stable results out of an unstable sort

from dataclasses import dataclass
@dataclass
class Row:
    name: str
    score: int
rows = [
    Row("A", 90),
    Row("B", 90),
    Row("C", 80),
]
# The index as secondary key forces input order on ties.
# With a stable sort it is redundant: rows.sort(key=lambda r: -r.score) gives the same result.
indexed = list(enumerate(rows))
indexed.sort(key=lambda t: (-t[1].score, t[0]))
ordered = [r for _, r in indexed]
print([r.name for r in ordered])  # ['A', 'B', 'C']

The index trick (a “decorate-sort-undecorate” pattern) is how you get stable results from an unstable sort, for example when implementing the sort yourself with quick sort or heap sort, or in a language whose default sort is not stable. With Python’s built-in sort you can rely on stability directly, which also enables multi-key sorting in passes: sort by the secondary key first, then by the primary key, and ties in the primary key keep the secondary order. The same holds for sorted(rows, key=..., reverse=True): reverse=True preserves the original order of equal elements, which is not the same as reversing the sorted list.

---

Choosing between quick, merge and heap sort

Need	Algorithm
Fastest average	Quick
Guaranteed O(n log n)	Merge or Heap
Stable	Merge
In-place	Quick or Heap
Nearly sorted	Insertion or Timsort

The failure that catches hand-written quick sort is its worst case. A pivot taken from the first or last position degrades to O(n²) on input that is already sorted or reverse-sorted, and a two-way partition degrades the same way when the array holds many equal values. A random or median-of-three pivot fixes the first problem and three-way partitioning fixes the second. Library sorts avoid the issue differently: C++ std::sort is introsort, which falls back to heap sort when recursion gets too deep, and Python uses Timsort, a merge-based stable sort.

Write merge sort when you need stability or are sorting linked lists or data that does not fit in memory; write heap sort when you need a worst-case bound with O(1) extra space. Otherwise use the language’s built-in sort. See also Basic Sorting (Bubble/Selection/Insertion).

---

Recommended Problems

Baekjoon

• 2751: Sorting Numbers 2

LeetCode

• LeetCode 215: Kth Largest Element in an Array
• LeetCode 912: Sort an Array
• LeetCode 88: Merge Sorted Array
• LeetCode 75: Sort Colors (Dutch National Flag)

Programmers

• Kth Number

---

Related Articles

• Sorting Algorithms
• Sorting Problems
• Binary Search
• Algorithm Series Full Index
• Arrays vs Linked Lists for Coding Interviews

---

Frequently Asked Questions (FAQ)

Q. Why can quick sort degrade to O(n²), and how do real implementations avoid it?

A. If the pivot is repeatedly the smallest or largest element, for example always taking the first element of already sorted input, each partition removes only one element and the recursion depth becomes n. Random pivots or median-of-three make that case unlikely, and introsort (used by many C++ std::sort implementations) switches to heap sort when recursion gets too deep. In Python, deep recursion can also hit the recursion limit before it gets slow.

---