Sorting and Searching Techniques

Algorithm trade-offs

Merge sort: O(n log n), stable, needs extra memory.
Quick sort: average O(n log n), in-place style, worst O(n^2).
Binary search needs sorted data and halves search space.

Merge sort implementation

Classic divide-and-conquer sort

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));
  const merged: number[] = [];

  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) merged.push(left[i++]);
    else merged.push(right[j++]);
  }

  return [...merged, ...left.slice(i), ...right.slice(j)];
}