Sorting Algorithms Compared — Bubble to Quick Sort

Nobody writes sorts at work (arr.sort() exists) — but interviews use them to test if you understand complexity trade-offs.

The lineup

• Bubble O(n²): repeatedly swap adjacent out-of-order pairs. Teaching tool only
• Selection O(n²): find min, put it first, repeat. Fewest swaps
• Insertion O(n²): like sorting cards in hand. O(n) on nearly-sorted data — that nuance impresses
• Merge O(n log n): split in half, sort halves, merge. Stable, predictable, needs O(n) extra space
• Quick O(n log n) avg: partition around a pivot. In-place and cache-friendly — but O(n²) worst case on sorted input with bad pivots

The merge step (what they actually ask you to write)

function merge(a, b) {
  const out = []; let i = 0, j = 0;
  while (i < a.length && j < b.length)
    out.push(a[i] <= b[j] ? a[i++] : b[j++]);
  return [...out, ...a.slice(i), ...b.slice(j)];
}

Questions that come up

• "Why is quicksort usually faster than mergesort despite same Big-O?" — constants: in-place, cache locality
• "What does STABLE mean?" — equal elements keep their original order (matters when sorting objects by one field)
• "What does JS use?" — V8: TimSort (merge+insertion hybrid), stable

Write the merge step on our judge.