Sorting Algorithms

Sorting is the most-studied problem in computing because so much else gets easy once data is ordered: binary search, deduplication, finding medians, merging streams. Knowing how the classic sorts work — and their trade-offs — is table stakes for interviews.

There is a hard theoretical floor: any comparison-based sort needs at least O(n log n) comparisons in the worst case. The O(n²) sorts below are still worth understanding because they build intuition and win on tiny or nearly-sorted inputs.

The O(n²) family

• Bubble sort — repeatedly swap adjacent out-of-order pairs; the largest "bubbles" to the end each pass. Mostly pedagogical.
• Insertion sort — grow a sorted prefix, inserting each new element into place. Excellent on small or nearly-sorted arrays; used inside real sorts as a base case.
• Selection sort — repeatedly pick the minimum of the rest and place it. Minimal writes, but always O(n²).

Merge sort — divide & conquer, guaranteed O(n log n)

Split the array in half, sort each half recursively, then merge the two sorted halves in linear time. The recursion is log n deep and each level does O(n) work → O(n log n) always. It is stable but needs O(n) extra space.

function mergeSort(a) {
  if (a.length <= 1) return a
  const mid = a.length >> 1
  const left = mergeSort(a.slice(0, mid))
  const right = mergeSort(a.slice(mid))
  const out = []
  let i = 0, j = 0
  while (i < left.length && j < right.length)
    out.push(left[i] <= right[j] ? left[i++] : right[j++])
  return [...out, ...left.slice(i), ...right.slice(j)]
}

Quick sort — fast in practice, O(n²) worst case

Pick a pivot, partition the array so smaller elements go left and larger go right, then recurse on each side. Average O(n log n) with great cache behavior and in-place O(log n) space — but a bad pivot on already-sorted data degrades to O(n²) (fix with a random or median-of-three pivot).