Skip to main content

Sorting Algorithms

Comparison-based and non-comparison sorting algorithms with their properties and use cases

TL;DR​

Sorting algorithms divide into comparison-based (merge, quick, heap) and non-comparison (counting, radix, bucket). Merge sort guarantees O(n log n) and stability but uses O(n) space. Quick sort averages O(n log n) with O(1) space but degrades to O(n²). Use counting/radix for bounded integer ranges; use heap when space is critical. Algorithm choice depends on data size, stability requirements, and whether data fits in memory.

Learning Objectives​

  • Understand time/space complexity trade-offs for major sorting algorithms
  • Recognize when stability matters and which algorithms preserve ordering
  • Implement efficient sorts for real-world constraints (memory, large datasets)
  • Choose optimal algorithms based on data characteristics and performance goals
  • Identify partition, divide-and-conquer, and non-comparison approaches

Motivating Scenario​

Your e-commerce platform sorts customer orders by date with payment status as a tiebreaker. Using an unstable sort scrambles the tiebreaker order, breaking reporting. Merging 100 million rows of analytics data with quick sort causes occasional 30-second pauses (O(n²) worst case). Counting sort on ZIP codes (5-digit) runs 10x faster than comparison sorts. Algorithm selection is not academic—it directly impacts user experience and infrastructure costs.

Core Concepts​

Sorting algorithm decision tree: compare data characteristics, memory constraints, and stability needs.

Comparison-based Sorts: Compare elements pairwise; lower bound is Ω(n log n) by information theory.

Non-comparison Sorts: Use element properties (digits, range) to avoid comparisons; can beat O(n log n) for specific inputs.

Stability: Preserves relative order of equal elements; critical for multi-key sorting or chained operations.

In-place: Uses O(1) extra space (or O(log n) for recursion); matters for large datasets or memory-constrained systems.

Practical Example​

def merge_sort(arr):
    """Divide-and-conquer: guaranteed O(n log n), stable, uses O(n) extra 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):
    """Merge two sorted arrays, preserving stability."""
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        # Left first: stable when left <= 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

# Usage: tuples with (priority, order_id)
orders = [(2, 'O123'), (1, 'O456'), (2, 'O789')]
sorted_orders = merge_sort(orders)  # Stable: (1, 'O456'), (2, 'O123'), (2, 'O789')

When to Use / When NOT to Use​

Merge Sort
  1. Always O(n log n), guaranteed stable
  2. Ideal for multi-key sorting (e.g., email by domain, then by date)
  3. External sorting for data larger than memory
  4. Drawback: uses O(n) extra space, slower due to copying
Quick Sort
  1. Average O(n log n) with O(log n) stack space (in-place)
  2. Fastest in practice; good cache locality
  3. Default for general-purpose sorting
  4. Drawback: O(n²) worst case (mitigated by random pivot or Timsort)
Heap Sort
  1. O(n log n) guaranteed, O(1) space, fully in-place
  2. Best when memory is extremely constrained
  3. Priority queue operations (extracting top k elements)
  4. Drawback: poor cache locality, unstable, slower in practice than quick sort
Counting / Radix Sort
  1. O(n+k) linear for small ranges or fixed-digit integers
  2. Unbeatably fast for discrete bounded data (digits, test scores, years)
  3. Stable by design
  4. Drawback: only for non-negative integers or mappable data; needs extra space

Patterns & Pitfalls​

Pattern: Stable Sort for Multi-Key Data
Sort by secondary key (date), then stable-sort by primary key (category). Elements with same primary key preserve date order. Merge sort or built-in stable sorts guarantee this.
Pattern: Hybrid Timsort
Combine insertion sort (small runs), merge sort (large runs), and galloping (skipping runs). Used by Python, Java, JavaScript V8. Leverages real-world data patterns for near-linear performance.
Pattern: Three-Way Partitioning (Quick Sort with Duplicates)
Partition into less-than, equal-to, greater-than. Handles duplicate elements efficiently, avoiding O(n²) degeneracy when many equal keys exist.
Pitfall: Unstable Sort Breaking Chained Operations
After sorting by date, sort by status. Non-stable sort scrambles date order. Use stable sorts or combine keys (tuples) into single sort key.
Pitfall: O(n²) Worst Case in Quick Sort
Median-of-three pivot, random pivot, or Timsort eliminates this. Never use basic quick sort on adversarially sorted data (reverse-sorted, all-same).
Pitfall: Counting Sort on Large Ranges
Counting sort: O(n+k) where k = range. If k >> n (e.g., 1 billion ZIP codes), counting sort uses too much memory. Use radix or comparison sorts instead.

Design Review Checklist​

  • Sorted by primary key and stable for secondary key?
  • Data is small enough to fit in memory, or is external sort needed?
  • Space constraint critical (in-place), or extra O(n) acceptable?
  • Range of values small (k << n) for counting/radix sort?
  • Worst-case performance guaranteed (merge/heap) or expected (quick)?
  • Duplicates handled efficiently (three-way partitioning, radix)?
  • Sorted order preserved in subsequent operations (stable sort)?
  • Performance tested on real data size and distribution?
  • Built-in sort (Timsort) sufficient, or custom sort needed?
  • Sort is not bottleneck; profiling confirms impact?

Self-Check​

  • Why is merge sort stable but quick sort is not?
  • When would you use counting sort over merge sort?
  • What does O(n log n) lower bound mean, and which sorts achieve it?
  • How does radix sort beat O(n log n), and what are the trade-offs?
  • What is "in-place" sorting, and why does it matter for large datasets?

Next Steps​

References​