Sorting Algorithm Comparison: When to Use Which

Sorting is the backbone of countless algorithms and applications. While most programmers reach for sort() without thinking, understanding when each algorithm shines helps you choose wisely—and prepares you for the interview questions that inevitably follow.

The key dimensions: time complexity (best/average/worst), space complexity, stability (does equal elements maintain their relative order?), and how the algorithm behaves with different input distributions.

Algorithm Overview

# Quick reference for complexities
def complexity_reference():
    """
    Algorithm          | Best       | Average    | Worst     | Space  | Stable |
    -------------------|------------|------------|-----------|--------|--------|
    Bubble Sort        | O(n)       | O(n²)      | O(n²)     | O(1)   | Yes    |
    Selection Sort     | O(n²)      | O(n²)      | O(n²)     | O(1)   | No     |
    Insertion Sort     | O(n)       | O(n²)      | O(n²)     | O(1)   | Yes    |
    Merge Sort         | O(n log n) | O(n log n) | O(n log n)| O(n)   | Yes    |
    Heap Sort          | O(n log n) | O(n log n) | O(n log n)| O(1)   | No     |
    Quick Sort         | O(n log n) | O(n log n) | O(n²)     | O(log n)| No    |
    Count Sort         | O(n + k)   | O(n + k)   | O(n + k)  | O(k)   | Yes    |
    Radix Sort         | O(nk)      | O(nk)      | O(nk)     | O(n + k)| Yes   |
    Timsort (Python)   | O(n)       | O(n log n) | O(n log n)| O(n)   | Yes    |
    """
    pass

Practical Implementation

def merge_sort(arr):
    """Stable, guaranteed O(n log n), but O(n) space."""
    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]:  # <= ensures stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


def quicksort(arr):
    """Not stable, O(n log n) average, O(n²) worst case."""
    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 quicksort(left) + middle + quicksort(right)


def heapsort(arr):
    """Not stable, O(n log n), O(1) space - good for memory constraints."""
    def heapify(arr, n, 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)

    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)

Stability Comparison

Algorithm	Stable?	Why?
Merge Sort	Yes	When merging, we process left array first on equal elements
Timsort	Yes	Designed to be stable
Insertion Sort	Yes	We only swap when strictly greater than
Bubble Sort	Yes	We swap only when strictly greater
Quick Sort	No	Partitioning can change relative order
Heap Sort	No	Heap property doesn’t preserve stability
Selection Sort	No	Finding minimum can skip elements

When to Use Each Algorithm

Use Merge Sort when

• You need stable sorting
• You need guaranteed O(n log n) worst case
• You’re working with linked lists (no random access)
• Memory isn’t severely constrained

Use Quick Sort when

• Average performance matters more than worst case
• Memory is limited (O(log n) stack space)
• You’re sorting arrays (random access is fast)
• Cache locality matters for your data

Use Heap Sort when

• Memory is very limited (O(1) space)
• You need guaranteed O(n log n) with less overhead than merge sort
• You don’t need stability

Use Insertion Sort when

• Input is nearly sorted (nearly sorted)
• Sorting small arrays (n < ~50)
• Data is being streamed and you need incremental sorting

Use Timsort (Python’s built-in) when

• You’re writing Python (just use sorted() or .sort())
• Data has natural runs (already sorted subsequences)

Input Distribution Matters

# Quick Sort's pivot choice dramatically affects performance

# Bad pivot (sorted array with middle pivot):
# [1, 2, 3, 4, 5] → pivot = 3 → partitions into [1, 2] and [4, 5]
# This recurses n-2 times → O(n²)

# Good pivot (median-of-three):
# Choose median of first, middle, last elements
# This protects against sorted input

# For nearly sorted arrays:
# Insertion Sort beats Quick Sort hands-down
# Even O(n²) insertion sort beats O(n log n) quicksort
# when the O(n²) is never triggered and quicksort has bad pivots

Trade-off Summary

Algorithm	Time (avg)	Space	Stable	Best Use Case
Quick Sort	O(n log n)	O(log n)	No	General purpose, arrays
Merge Sort	O(n log n)	O(n)	Yes	Stable, linked lists
Heap Sort	O(n log n)	O(1)	No	Memory-constrained
Timsort	O(n log n)	O(n)	Yes	Python default
Insertion	O(n²)	O(1)	Yes	Nearly sorted, small n

Production Failure Scenarios

1. Quick Sort with bad pivot on sorted input: O(n²) instead of O(n log n)—use randomized pivot or median-of-three
2. Merge Sort stack overflow on large arrays: Recursion depth can hit limit—use iterative merge sort or increase recursion limit
3. Heap Sort not stable for multi-key sorting: When sorting by multiple keys, instability corrupts secondary sort order

Quick Recap Checklist

• Quick Sort: fast average case, not stable, O(log n) space
• Merge Sort: stable, guaranteed O(n log n), O(n) space
• Heap Sort: not stable, O(1) space, good for memory constraints
• Insertion Sort: stable, O(1) space, best for small/nearly sorted data
• Timsort: Python’s hybrid, exploits natural runs in data
• Never use Bubble/Selection sort in production—they’re teaching tools

Interview Q&A