Sorting Algorithm Deep Dive: Quicksort, Mergesort, Heapsort, and Counting Sort (2025)

Why Sorting Algorithms Still Matter in Interviews

Interviewers at top tech companies still ask about sorting not to test memorization, but to probe your understanding of time-space tradeoffs, stability requirements, and how to reason about algorithm selection under constraints. This guide covers the four families you need cold.

Quicksort

Quicksort is the go-to in-place, cache-friendly sort for general-purpose use. Average O(n log n), worst-case O(n^2) (degenerate pivot), O(log n) stack space.

Lomuto Partition

def quicksort_lomuto(arr, lo, hi):
    if lo < hi:
        p = partition_lomuto(arr, lo, hi)
        quicksort_lomuto(arr, lo, p - 1)
        quicksort_lomuto(arr, p + 1, hi)

def partition_lomuto(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

Hoare Partition

Hoare’s original scheme uses two inward-moving pointers and does fewer swaps on average than Lomuto. The pivot ends up somewhere in the middle, not necessarily at the returned index.

def partition_hoare(arr, lo, hi):
    pivot = arr[(lo + hi) // 2]
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while arr[i]  pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

Random Pivot – The Critical Optimization

Always use a random pivot (or median-of-three) in production. A sorted or reverse-sorted input will trigger worst-case O(n^2) on a naive pivot=last implementation. Randomization makes worst case astronomically unlikely.

import random

def quicksort(arr, lo, hi):
    if lo < hi:
        # Random pivot: swap random element with hi before partition
        rand_idx = random.randint(lo, hi)
        arr[rand_idx], arr[hi] = arr[hi], arr[rand_idx]
        p = partition_lomuto(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)

When to Use Quicksort

General-purpose in-memory sorting where stability is not required
Cache performance matters (in-place, sequential access pattern)
Average-case speed is priority (smaller constant factor than mergesort)
Avoid when: you need stable sort, or worst-case guarantees matter (use heapsort or mergesort)

Mergesort

Mergesort guarantees O(n log n) in all cases and is stable – equal elements maintain their original order. The cost is O(n) auxiliary space.

def mergesort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        # <= preserves stability (left wins ties)
        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

External Sort Use Case

Mergesort is the foundation for external sorting – sorting datasets larger than RAM. The algorithm maps naturally to a k-way merge of sorted runs on disk. Classic interview scenario: “sort 100 GB of data with 4 GB RAM” – create sorted 4 GB chunks, then k-way merge using a min-heap.

When to Use Mergesort

Stability required (sorting objects with multiple keys, e.g., sort by last name then first name)
Linked lists (mergesort works naturally, no random access needed)
External sorting (disk-based large datasets)
Predictable O(n log n) required even in worst case

Heapsort

Heapsort achieves O(n log n) worst case and O(1) extra space (in-place). It builds a max-heap, then repeatedly extracts the maximum.

def heapsort(arr):
    n = len(arr)
    # Build max-heap (heapify from last non-leaf upward)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # move max to end
        sift_down(arr, i, 0)

def sift_down(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2
    if left  arr[largest]:
        largest = left
    if right  arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        sift_down(arr, n, largest)

Why Heapsort is Rarely Used in Practice

Despite its theoretical advantages, heapsort has poor cache behavior. Heap access patterns jump around memory unpredictably, causing frequent cache misses. Quicksort with good pivot selection is 2-5x faster in practice on modern hardware despite the same O(n log n) average.

When Heapsort Wins

O(1) auxiliary space is a hard requirement (embedded systems)
Worst-case O(n log n) required AND O(1) space (mergesort needs O(n))
Finding top-k elements efficiently – stop after k extractions from the heap

Counting Sort and Radix Sort

These non-comparison sorts break the O(n log n) lower bound when the input domain is bounded integers.

Counting Sort – O(n + k)

def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1
    # Cumulative count for stable version
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    output = [0] * len(arr)
    for x in reversed(arr):  # reversed for stability
        count[x] -= 1
        output[count[x]] = x
    return output

Complexity: O(n + k) time and space, where k = range of values. Practical when k = O(n) – e.g., sorting exam scores (0-100), ages, character frequencies.

Radix Sort – O(d * (n + k))

Radix sort applies counting sort digit by digit (LSD – least significant digit first). For integers with d digits in base k: O(d * (n + k)). For 32-bit integers with base 256: d=4 passes, each O(n + 256) – effectively O(n).

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for i in arr:
        index = (i // exp) % 10
        count[index] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        count[index] -= 1
        output[count[index]] = arr[i]
    for i in range(n):
        arr[i] = output[i]

Python’s Timsort

Python’s built-in sorted() and list.sort() use Timsort – a hybrid algorithm that combines mergesort and insertion sort. Understanding Timsort earns you points in Python-focused interviews.

Stable: equal elements preserve original order
Adaptive: O(n) on already-sorted or reverse-sorted input (detects natural runs)
Hybrid: uses insertion sort for small runs (size < 64), then merges runs bottom-up
Worst case: O(n log n), guaranteed
Space: O(n) for merging

Timsort identifies existing sorted “runs” in the data and merges them. On real-world data (partially sorted, reverse-sorted sections), it dramatically outperforms pure quicksort or mergesort.

Comparison Table: Which Sort for Which Situation

Algorithm	Avg Time	Worst Time	Space	Stable	Best For
Quicksort	O(n log n)	O(n^2)	O(log n)	No	General purpose, cache-friendly, primitives
Mergesort	O(n log n)	O(n log n)	O(n)	Yes	Stable sort, linked lists, external sort
Heapsort	O(n log n)	O(n log n)	O(1)	No	In-place + worst-case guarantee, top-k
Counting Sort	O(n + k)	O(n + k)	O(k)	Yes	Small integer range, frequency problems
Radix Sort	O(d(n+k))	O(d(n+k))	O(n+k)	Yes	Large integer arrays with fixed digit count
Timsort	O(n log n)	O(n log n)	O(n)	Yes	Real-world data, nearly-sorted input

Interview Decision Framework

Default answer: “Use the language’s built-in sort (Timsort in Python, introsort in C++)” – always say this first
Need stability? Mergesort or Timsort
O(1) space + worst-case guarantee? Heapsort
Integer keys with bounded range? Counting sort or radix sort
Implementing from scratch for interview? Quicksort with random pivot – cleanest to code, easiest to explain
Sorted/nearly-sorted input? Insertion sort (O(n) best case) or Timsort
External/disk sort? Mergesort-based k-way merge

Common Interview Mistakes

Using pivot=last on potentially sorted input without randomization
Forgetting that counting sort only works on non-negative integers (needs offset for negatives)
Claiming quicksort is always O(n log n) – it is not, worst case is O(n^2)
Not mentioning stability when sorting objects with multiple fields
Off-by-one errors in Hoare partition (the index returned is NOT the final pivot position)

Frequently Asked Questions

What sorting algorithm should I use in a coding interview?

Default to the language’s built-in sort (Python’s Timsort, C++’s introsort). If asked to implement from scratch, use quicksort with random pivot for general arrays. Use mergesort when stability is required. Use counting or radix sort when the input is bounded integers. Always state your reasoning before coding.

Why is quicksort O(n^2) in the worst case and how do you avoid it?

Quicksort degrades to O(n^2) when the pivot consistently splits the array into one empty and one n-1 element partition – this happens with sorted or reverse-sorted input if you always pick the first or last element as pivot. The fix is random pivot selection: choose a random index, swap it to the pivot position before partitioning. This makes worst-case input astronomically unlikely in practice.

What does stable sort mean and why does it matter?

A stable sort preserves the relative order of equal elements. For example, if you have records sorted by last name and then sort by first name stably, records with the same first name remain in last-name order. Mergesort and Timsort are stable. Quicksort and heapsort are not. Stability matters whenever you sort objects with multiple keys or need reproducible output.

When would you use counting sort over quicksort?

Counting sort is O(n+k) and beats comparison-based O(n log n) sorts when k (the value range) is O(n). Classic use cases: sorting exam scores (0-100), sorting ages, character frequency problems, bucket problems with small integer values. It only works on non-negative integers (or integers with a fixed offset). For large or unknown ranges, stick with quicksort or mergesort.

What is Timsort and why does Python use it?

Timsort is a hybrid algorithm combining mergesort and insertion sort, developed by Tim Peters for Python in 2002. It detects existing sorted “runs” in the data and merges them bottom-up. On already-sorted or nearly-sorted data it runs in O(n). It is always O(n log n) worst case, stable, and performs extremely well on real-world data that often contains partially sorted sections. Java uses a variant of Timsort for object arrays as well.