Sorting Algorithms: Complete Guide

Sorting is one of the most fundamental algorithmic problems. Understanding sorting algorithms teaches you algorithm design patterns.

Comparison Sorts

Limited by O(n log n) comparisons in the worst case.

Quick Sort

Divide and conquer: pick a pivot, partition, recurse.

def quicksort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        quicksort(arr, low, pivot - 1)
        quicksort(arr, pivot + 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

Use when: Fast average performance, in-place sorting needed. Use randomized pivot or median-of-three to avoid worst case.

Merge Sort

Divide, recursively sort, merge.

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):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    return result + left[i:] + right[j:]

Use when: Stable sort needed, linked lists (O(1) merge), guaranteed O(n log n) required.

Heap Sort

Build heap, extract repeatedly:

def heapsort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):  # heapify
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # extract max
        heapify(arr, i, 0)

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)

Use when: Memory is extremely tight, guaranteed O(n log n) required.

Insertion Sort

Build sorted output one element at a time.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

| Metric | Value | |

Non-Comparison Sorts

Counting Sort

Count occurrences, reconstruct sorted array. O(n + k) where k is the value range.

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

Use when: Integer keys with small range.

Radix Sort

Sort digit by digit (least significant to most):

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

Use when: Fixed-width integer keys, large n.

Comparison

Practical Guidelines

• N < 50: Insertion sort (simple, cache-friendly)
• N < 10M: Quicksort (default, fast in practice)
• Need stability: Merge sort or Timsort
• Tight memory: Heap sort
• Small integer keys: Counting sort
• Fixed-width integers: Radix sort

Most language standard libraries use Timsort (Python, Java, JS) — a hybrid of merge and insertion sort.

Sorting Algorithm Categories

Comparison-Based Sorting

Comparison sorts work by comparing elements pairwise and rearranging them based on comparison results. The theoretical lower bound for comparison-based sorting is O(n log n) comparisons — any algorithm that only uses comparisons to determine order must perform at least log(n!) ≈ n log n comparisons in the worst case. Merge sort achieves O(n log n) time in all cases with O(n) space. Heapsort also achieves O(n log n) worst-case time with O(1) space using a binary heap data structure. Quicksort averages O(n log n) but degrades to O(n²) with poor pivot selection — mitigated by randomized pivot selection or the median-of-three strategy. Timsort, the default sorting algorithm in Python and Java, combines merge sort and insertion sort, exploiting existing order in real-world data to achieve near-linear time on partially sorted arrays.

Non-Comparison Sorting

Integer sorting algorithms leverage the numerical properties of keys rather than comparisons. Counting sort counts occurrences of each key value and uses the cumulative counts to place elements directly in sorted position — it runs in O(n + k) time where k is the range of key values and requires O(k) space. Radix sort sorts digit by digit using counting sort as a subroutine, achieving O(d × (n + k)) where d is the number of digits and k is the digit range. Bucket sort distributes elements into buckets based on their value range, sorts each bucket individually (usually with insertion sort), and concatenates the buckets. These algorithms achieve linear time when k is small relative to n, making them practical for sorting large arrays of integers with limited range — sorting 10 million 32-bit integers is faster with radix sort than comparison-based alternatives.

Practical Sorting Considerations

Choosing a sorting algorithm for production code depends on data characteristics. For nearly sorted data (common in database query results), insertion sort and Timsort excel. For data too large to fit in memory, external merge sort divides the data into blocks that fit in memory, sorts each block, and merges them using a tournament tree. In distributed systems, MapReduce-style sorting uses parallel partitioning and merging across nodes. Stability — whether equal elements maintain their original relative order — matters when sorting by multiple keys: stable sorts preserve the order from earlier sort passes. Timsort’s stability is a key advantage for multi-key sorting. For embedded systems with limited memory, heapsort’s O(1) space is often preferred despite lower constant factors.

Sorting in Practice

Hybrid Sorting Algorithms

Modern production sorting systems rarely use a single algorithm. Introsort begins with quicksort, switches to heapsort when recursion depth exceeds log(n), and uses insertion sort for small partitions (typically fewer than 16 elements). This hybrid approach guarantees O(n log n) worst-case performance while maintaining quicksort’s speed on average. Timsort, used in Python, Java, and Android, identifies naturally occurring runs (already sorted subsequences) in the data, merges them efficiently, and uses galloping mode when one run consistently dominates. For nearly sorted data, Timsort achieves O(n) time. PDQSort (Pattern-defeating Quicksort) uses median-of-medians pivot selection and block partitioning for better performance on adversarial inputs.

External Sorting

When data exceeds available memory, external sorting uses disk storage. The external merge sort algorithm divides the input into chunks that fit in memory, sorts each chunk (producing sorted runs), and merges runs using a priority queue. The number of passes depends on the data size and available memory: sorting 1 TB with 1 GB of memory requires two passes (1000 initial runs, then one merge pass with 1000-way merging). Replacement selection produces runs of approximately 2× memory size by using a heap that outputs the smallest element and replaces it with the next input element. Tournament trees enable k-way merging with O(log k) complexity per element. Modern external sorting also considers SSD characteristics — sequential access is still faster than random access, but SSDs reduce the penalty compared to HDDs.

Frequently Asked Questions

What is the fastest sorting algorithm? There is no single fastest algorithm for all scenarios. Quicksort with median-of-three pivot selection is typically fastest on random data. Timsort is fastest on real-world data with existing order. For integers with limited range, counting sort and radix sort outperform comparison-based algorithms. The fastest choice depends on data size, distribution, and hardware characteristics.

Why is O(n log n) the lower bound for comparison sorting? The decision tree model for comparison sorting has n! possible output permutations. Each comparison has two outcomes, so the decision tree has at most 2^h leaves for height h. To have at least n! leaves, we need 2^h ≥ n!, so h ≥ log(n!) ≈ n log n. This lower bound does not apply to non-comparison sorts that use the numerical properties of keys.

When should I use merge sort vs quicksort? Use merge sort when stable sorting is required, when data is too large for in-memory sorting (external merge sort), or when guaranteed O(n log n) performance is critical. Use quicksort when in-place sorting is preferred, when average-case performance matters more than worst-case guarantees, and when extra space is limited. In practice, Timsort merges the advantages of both.

Heaps Guide — Searching Algorithms Guide — Hash Tables Guide