Sorting Algorithms Cheat Sheet: Complexity, Code & When to Use

Sorting is one of the most studied problems in computer science. The right algorithm can cut your runtime from minutes to milliseconds — and the wrong one can grind production to a halt. This cheat sheet covers every major sorting algorithm with complexity tables, working code, and concrete guidance on when to use each.

Quick reference

k = range of input values. Stable = equal elements preserve original order.

TL;DR for 80% of cases: use your language's built-in sort (Tim sort in Python/Java, introsort in C++, V8's Tim sort in JavaScript). Only reach for a custom algorithm when you have a specific constraint — huge n, tiny range of values, nearly-sorted input, or memory limits.

Bubble sort

The simplest sorting algorithm. Repeatedly steps through the list, swaps adjacent elements that are out of order, and repeats until no swaps are needed.

Use when: teaching sorting concepts. Never in production for large n.

// JavaScript
function bubbleSort(arr) {
  const a = [...arr];
  let n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - i - 1; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]]; // swap
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted — O(n) best case
  }
  return a;
}

bubbleSort([64, 34, 25, 12, 22, 11, 90]);
// [11, 12, 22, 25, 34, 64, 90]

# Python
def bubble_sort(arr):
    a = arr[:]
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a

// Go
func bubbleSort(arr []int) []int {
    a := append([]int{}, arr...)
    n := len(a)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-i-1; j++ {
            if a[j] > a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
                swapped = true
            }
        }
        if !swapped {
            break
        }
    }
    return a
}

// PHP
function bubbleSort(array $arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false;
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
            }
        }
        if (!$swapped) break;
    }
    return $arr;
}

Selection sort

Finds the minimum element in the unsorted portion and places it at the beginning. Makes the minimum number of swaps (O(n)), but always O(n²) comparisons — can't short-circuit like bubble sort.

Use when: write operations are expensive (e.g., flash memory) and n is small.

// JavaScript
function selectionSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[minIdx]) minIdx = j;
    }
    if (minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]];
  }
  return a;
}

# Python
def selection_sort(arr):
    a = arr[:]
    n = len(a)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]
    return a

Insertion sort

Builds the sorted array one item at a time by inserting each new element into its correct position among already-sorted elements. Excellent for small or nearly-sorted arrays — it's the algorithm Tim sort falls back to for small runs.

Use when: n < 20, or the array is nearly sorted (mostly O(n)).

// JavaScript
function insertionSort(arr) {
  const a = [...arr];
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
  return a;
}

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

// Go
func insertionSort(arr []int) []int {
    a := append([]int{}, arr...)
    for i := 1; i < len(a); i++ {
        key := a[i]
        j := i - 1
        for j >= 0 && a[j] > key {
            a[j+1] = a[j]
            j--
        }
        a[j+1] = key
    }
    return a
}

Merge sort

Divide-and-conquer algorithm that splits the array in half, recursively sorts both halves, then merges them. Guaranteed O(n log n) in all cases — never degrades. The downside is O(n) auxiliary space.

Use when: you need guaranteed O(n log n), stable sort, or sorting linked lists (merge sort works naturally on linked lists with O(1) extra space).

// JavaScript
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

mergeSort([38, 27, 43, 3, 9, 82, 10]);
// [3, 9, 10, 27, 38, 43, 82]

# Python
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

// Go
func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return append([]int{}, arr...)
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return mergeSorted(left, right)
}

func mergeSorted(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i]); i++
        } else {
            result = append(result, right[j]); j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

Quicksort

Divide-and-conquer algorithm that picks a pivot, partitions the array so elements smaller than the pivot are left and larger are right, then recursively sorts both partitions. Average O(n log n) with excellent cache performance in practice — often faster than merge sort on real data despite same asymptotic complexity.

Use when: general-purpose sorting of arrays in memory where you don't need stability. Avoid on nearly-sorted data with naive pivot selection.

// JavaScript — Lomuto partition with random pivot
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}

function partition(arr, lo, hi) {
  // Random pivot to avoid O(n²) on sorted input
  const pivotIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[pivotIdx], arr[hi]] = [arr[hi], arr[pivotIdx]];
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

const data = [10, 7, 8, 9, 1, 5];
quickSort(data);
// [1, 5, 7, 8, 9, 10]

# Python
import random

def quick_sort(arr, lo=0, hi=None):
    if hi is None:
        arr = arr[:]
        hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quick_sort(arr, lo, p - 1)
        quick_sort(arr, p + 1, hi)
    return arr

def partition(arr, lo, hi):
    pivot_idx = random.randint(lo, hi)
    arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
    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

// Go
func quickSort(arr []int, lo, hi int) {
    if lo < hi {
        p := partitionGo(arr, lo, hi)
        quickSort(arr, lo, p-1)
        quickSort(arr, p+1, hi)
    }
}

func partitionGo(arr []int, lo, hi int) int {
    // median-of-three pivot
    mid := lo + (hi-lo)/2
    if arr[lo] > arr[mid] { arr[lo], arr[mid] = arr[mid], arr[lo] }
    if arr[lo] > arr[hi]  { arr[lo], arr[hi]  = arr[hi],  arr[lo] }
    if arr[mid] > arr[hi] { arr[mid], arr[hi] = arr[hi], arr[mid] }
    arr[mid], arr[hi] = arr[hi], arr[mid]
    pivot := arr[hi]
    i := lo - 1
    for j := lo; j < hi; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1
}

Heap sort

Uses a binary max-heap to sort. First builds a heap in O(n), then extracts the maximum element n times, each in O(log n). Guaranteed O(n log n) worst case with O(1) space — better space than merge sort, better worst case than quicksort.

Use when: you need guaranteed O(n log n) and O(1) extra space, and don't need stability.

// JavaScript
function heapSort(arr) {
  const a = [...arr];
  const n = a.length;
  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(a, n, i);
  // Extract elements one by one
  for (let i = n - 1; i > 0; i--) {
    [a[0], a[i]] = [a[i], a[0]]; // move current root to end
    heapify(a, i, 0);
  }
  return a;
}

function heapify(arr, n, i) {
  let largest = i;
  const l = 2 * i + 1, r = 2 * i + 2;
  if (l < n && arr[l] > arr[largest]) largest = l;
  if (r < n && arr[r] > arr[largest]) largest = r;
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

# Python
def heap_sort(arr):
    a = arr[:]
    n = len(a)

    def heapify(arr, n, i):
        largest = i
        l, r = 2*i+1, 2*i+2
        if l < n and arr[l] > arr[largest]: largest = l
        if r < n and arr[r] > arr[largest]: largest = r
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)

    for i in range(n // 2 - 1, -1, -1):
        heapify(a, n, i)
    for i in range(n - 1, 0, -1):
        a[0], a[i] = a[i], a[0]
        heapify(a, i, 0)
    return a

Counting sort

Non-comparison sort that counts occurrences of each value, then reconstructs the sorted array. O(n+k) where k is the range of values. Incredibly fast when k is small relative to n (e.g., sorting grades 0–100 for a million students).

Use when: elements are integers (or can be mapped to integers) with a small known range. Sorting 10M array elements where values are 0–1000 → counting sort wins decisively.

// JavaScript
function countingSort(arr, maxVal) {
  const count = new Array(maxVal + 1).fill(0);
  for (const x of arr) count[x]++;
  // Prefix sum for stable output
  for (let i = 1; i <= maxVal; i++) count[i] += count[i - 1];
  const output = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }
  return output;
}

countingSort([4, 2, 2, 8, 3, 3, 1], 8);
// [1, 2, 2, 3, 3, 4, 8]

# Python
def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1
    # prefix sum
    for i in range(1, max_val + 1):
        count[i] += count[i - 1]
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
    return output

Radix sort

Sorts integers digit by digit, from least significant digit (LSD) to most significant digit (MSD), using counting sort as a subroutine at each digit position. O(nk) where k is the number of digits. Stable and very fast for integers.

Use when: sorting large arrays of integers (or fixed-length strings). Sorting 10M 32-bit integers → radix sort (4 passes of counting sort on 8-bit digits) is very fast.

// JavaScript — LSD Radix Sort (base 10)
function radixSort(arr) {
  const max = Math.max(...arr);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    arr = countingSortByDigit(arr, exp);
  }
  return arr;
}

function countingSortByDigit(arr, exp) {
  const output = new Array(arr.length);
  const count = new Array(10).fill(0);
  for (const x of arr) count[Math.floor(x / exp) % 10]++;
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];
  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }
  return output;
}

# Python
def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = 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 x in arr:
        count[(x // exp) % 10] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    for i in range(n - 1, -1, -1):
        d = (arr[i] // exp) % 10
        output[count[d] - 1] = arr[i]
        count[d] -= 1
    return output

Built-in sorts (what you should actually use)

Custom comparator examples:

// Sort objects by age descending, then name ascending
users.sort((a, b) => b.age - a.age || a.name.localeCompare(b.name));

# Sort tuples by second element, stable
data.sort(key=lambda x: x[1])
# Multiple keys: sort by category asc, price desc
products.sort(key=lambda p: (p['category'], -p['price']))

// Go 1.21+
import "slices"
slices.SortFunc(users, func(a, b User) int {
    if a.Age != b.Age {
        return b.Age - a.Age // descending age
    }
    return strings.Compare(a.Name, b.Name)
})

// PHP
usort($products, fn($a, $b) => $a['price'] <=> $b['price']);

When to use which algorithm

Common mistakes

Complexity summary

FAQ

Why is quicksort often faster than merge sort despite the same O(n log n) average? Cache locality. Quicksort works in-place, operating on contiguous memory with fewer cache misses. Merge sort allocates auxiliary arrays, causing more cache pressure. In practice, quicksort's constants are smaller.

When does quicksort hit O(n²)? When the pivot is consistently the smallest or largest element — worst case for naive pivot selection on already-sorted or reverse-sorted data. Random pivot selection or median-of-three reduces this to astronomically unlikely.

Is JavaScript's Array.sort() stable? Yes, since ES2019 (ECMAScript 2019) the specification requires stable sort. All modern engines (V8/SpiderMonkey/JavaScriptCore) implement this with Tim sort. Pre-2019 V8 used unstable quicksort for arrays > 10 elements.

Can I sort strings with these algorithms? Yes — replace numeric comparisons with string comparison (localeCompare, strcmp, strings.Compare). For locale-aware sorting (handles accented characters, language rules), always use localeCompare in JavaScript or locale.strxfrm in Python.

What is Tim sort? Tim sort (named after Tim Peters who invented it for Python in 2002) is a hybrid algorithm that uses insertion sort for small runs and merge sort to combine them. It detects existing sorted runs in the input, making it O(n) on nearly-sorted data. It's now the default in Python, Java, and modern JavaScript engines.

Radix sort has O(nk) complexity — isn't that worse than O(n log n)? It depends on k (the number of digits). For 32-bit integers, k = 4 (sorting by 8-bit digits in 4 passes). So radix sort runs in effectively 4 × O(n) = O(n) for typical integers, which beats O(n log n) at large n. At n = 10 million, radix sort is typically 2–4× faster than comparison sorts.