Sorting Algorithms

Core sorting algorithms with JavaScript implementations, time/space complexity, and when to use each one.

Complexity Cheatsheet

Algorithm        Best        Average     Worst       Space   Stable
────────────────────────────────────────────────────────────────────
Bubble Sort      O(n)        O(n²)       O(n²)       O(1)    Yes
Insertion Sort   O(n)        O(n²)       O(n²)       O(1)    Yes
Selection Sort   O(n²)       O(n²)       O(n²)       O(1)    No
Merge Sort       O(n log n)  O(n log n)  O(n log n)  O(n)    Yes
Quick Sort       O(n log n)  O(n log n)  O(n²)       O(log n) No
Heap Sort        O(n log n)  O(n log n)  O(n log n)  O(1)    No
Counting 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

Pick:
- General purpose      -> Quick Sort (fast average case, in-place)
- Need stable sort     -> Merge Sort
- Nearly sorted input  -> Insertion Sort
- Small integer range  -> Counting Sort or Radix Sort
- Memory constrained   -> Heap Sort (O(1) space)

Bubble Sort & Insertion Sort

// Bubble Sort — O(n²) avg, O(n) best (already sorted)
// Repeatedly swap adjacent elements if out of order
function bubbleSort(arr: number[]): number[] {
  const a = [...arr];
  const 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]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted — early exit
  }
  return a;
}

// Insertion Sort — O(n²) avg, O(n) best
// Great for small arrays or nearly-sorted data
function insertionSort(arr: number[]): number[] {
  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;
}

console.log(bubbleSort([5, 3, 1, 4, 2]));    // [1, 2, 3, 4, 5]
console.log(insertionSort([5, 3, 1, 4, 2])); // [1, 2, 3, 4, 5]

Merge Sort

// Merge Sort — O(n log n) all cases, O(n) space, stable
// Divide-and-conquer: split in half, sort each half, merge
function mergeSort(arr: number[]): number[] {
  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: number[], right: number[]): number[] {
  const result: number[] = [];
  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++]);
    }
  }
  // Append remaining elements
  return [...result, ...left.slice(i), ...right.slice(j)];
}

// Generic merge sort (works with any comparable type)
function mergeSortGeneric<T>(arr: T[], compareFn: (a: T, b: T) => number): T[] {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSortGeneric(arr.slice(0, mid), compareFn);
  const right = mergeSortGeneric(arr.slice(mid), compareFn);
  const result: T[] = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    result.push(compareFn(left[i], right[j]) <= 0 ? left[i++] : right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

// Sort objects by a property
const users = [{name: 'Bob', age: 30}, {name: 'Alice', age: 25}];
mergeSortGeneric(users, (a, b) => a.age - b.age);
// [{name: 'Alice', age: 25}, {name: 'Bob', age: 30}]

Quick Sort

// Quick Sort — O(n log n) avg, O(n²) worst (bad pivot), O(log n) space
// In-place: choose pivot, partition around it, recurse on both sides
function quickSort(arr: number[], lo = 0, hi = arr.length - 1): number[] {
  if (lo < hi) {
    const pivotIdx = partition(arr, lo, hi);
    quickSort(arr, lo, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, hi);
  }
  return arr;
}

// Lomuto partition scheme — pivot is last element
function partition(arr: number[], lo: number, hi: number): number {
  const pivot = arr[hi];
  let i = lo - 1;  // index of smaller element
  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;
}

// Median-of-three pivot selection (avoids worst case on sorted input)
function medianOfThree(arr: number[], lo: number, hi: number): number {
  const mid = Math.floor((lo + hi) / 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]];
  return mid; // arr[mid] is now the median
}

const arr = [3, 6, 8, 10, 1, 2, 1];
quickSort(arr);  // modifies in-place: [1, 1, 2, 3, 6, 8, 10]