Skip to main content

Sorting and Searching

Searching and sorting are where complexity theory pays off most directly: the difference between O(n) and O(log n) lookups, or O(n^2) and O(n log n) sorts, is the difference between code that scales and code that does not.

If the data is sorted, you never need to scan it. Compare against the middle, discard the half that cannot contain the target, repeat:

function binarySearch(sorted, target) {
  let lo = 0;
  let hi = sorted.length - 1;

  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

const ids = [3, 8, 15, 23, 42, 57, 91];
console.log(binarySearch(ids, 42)); // 4
console.log(binarySearch(ids, 50)); // -1

O(log n): a million elements resolve in at most 20 comparisons. The classic implementation bugs to avoid:

  • Off-by-one boundaries. Loop while lo <= hi, and move to mid + 1 / mid - 1, never to mid itself — that causes infinite loops.
  • Unsorted input. Binary search on unsorted data returns garbage, not an error.
  • Textbooks compute the midpoint as lo + (hi - lo) / 2 to avoid integer overflow; JavaScript numbers make this a non-issue at realistic sizes, but expect the question in interviews.

Binary search generalizes beyond exact matches: first/last occurrence, smallest element satisfying a condition, search in a rotated sorted array. Any monotonic "no no no yes yes yes" condition can be binary-searched.

When is sorting first worth it?​

Searching an unsorted array once is O(n) — sorting first would cost O(n log n) and gain nothing. Sorting pays when you search repeatedly: sort once, then answer q queries at O(log n) each instead of O(n) each. For pure membership checks, a Set beats both.

The classic sorts​

AlgorithmAverageWorstSpaceStableNotes
Bubble sortO(n^2)O(n^2)O(1)YesTeaching tool, never used in practice
Insertion sortO(n^2)O(n^2)O(1)YesExcellent on tiny or nearly-sorted data
Selection sortO(n^2)O(n^2)O(1)NoMinimal swaps, otherwise unremarkable
Merge sortO(n log n)O(n log n)O(n)YesPredictable, the standard divide-and-conquer
QuicksortO(n log n)O(n^2)O(log n)NoFast in practice, worst case on adversarial input
Heap sortO(n log n)O(n log n)O(1)NoIn-place guaranteed O(n log n)

Stable means equal elements keep their original relative order — it matters when sorting by one field of records that were already ordered by another.

Insertion sort​

Grow a sorted prefix by inserting each new element into its place — how most people sort playing cards:

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

console.log(insertionSort([5, 2, 9, 1, 7])); // [1, 2, 5, 7, 9]

Quadratic in general, but O(n) on nearly-sorted input — which is why production sorts hand small partitions to insertion sort.

Merge sort​

Split in half, sort each half, merge two sorted halves. The merge step is where the work happens:

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));

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

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10])); // [3, 9, 10, 27, 38, 43, 82]

log n levels of splitting, O(n) merge work per level: O(n log n) always. The merge technique itself — walking two sorted sequences with two pointers — reappears constantly: merging sorted lists, intersecting sorted arrays, counting inversions.

When to just use .sort​

Almost always. Array.prototype.sort is a highly tuned O(n log n) hybrid, and the spec has guaranteed stability since ES2019. Implementing quicksort by hand is for interviews; calling .sort is for everything else.

The one real gotcha — the default comparator sorts by string representation, even for numbers:

console.log([10, 1, 5, 2].sort()); // [1, 10, 2, 5]  — lexicographic!
console.log([10, 1, 5, 2].sort((a, b) => a - b)); // [1, 2, 5, 10]

The comparator contract: return a negative number to put a first, positive to put b first, zero to treat them as equal.

const team = [
  { name: "Hafsa", score: 92 },
  { name: "Rizwan", score: 78 },
  { name: "Zakariya", score: 92 },
  { name: "Ayesha", score: 85 },
];

team.sort((a, b) => b.score - a.score || a.name.localeCompare(b.name));
console.log(team.map((m) => m.name)); // ["Hafsa", "Zakariya", "Ayesha", "Rizwan"]

The || chains tie-breakers: sort by score descending, then by name for equal scores. Two more notes:

  • .sort mutates the array. Use arr.toSorted(cmp) (ES2023) or sort a copy when the original must survive.
  • For human-friendly string order, use a.localeCompare(b) instead of comparison operators.

When might you not use .sort? When you do not need a full sort: the k largest items (a heap, or quickselect at O(n) average), values from a tiny fixed range (counting sort at O(n + k)), or checking whether data is already sorted (a single O(n) scan).

Practice problems: the Sorting and Divide & Conquer sections of the practice catalog — the binary search problems live under Divide & Conquer.

Last updated on