Algorithms Lesson 9: Sorting Algorithms

Sorting is fundamental. Knowing HOW sorting works (not just arr.sort()) is essential for interviews and understanding performance tradeoffs.

Merge Sort — O(n log n)

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 l = 0, r = 0;
  while (l < left.length && r < right.length) {
    if (left[l] <= right[r]) result.push(left[l++]);
    else result.push(right[r++]);
  }
  return [...result, ...left.slice(l), ...right.slice(r)];
}
// Stable, O(n log n) always, O(n) space

Quick Sort — O(n log n) average

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  
  // Partition around pivot
  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]];
  const pivotIdx = i + 1;
  
  quickSort(arr, lo, pivotIdx - 1);
  quickSort(arr, pivotIdx + 1, hi);
  return arr;
}
// In-place O(1) space, O(n log n) avg, O(n²) worst

When to Use Which

// Merge Sort: when stability matters, or sorting linked lists
// Quick Sort: in-place, cache-friendly — fastest in practice
// Heap Sort: guaranteed O(n log n), O(1) space
// Counting Sort: O(n) when values are in known small range
// Radix Sort: O(n) for integers