Sorting fundamentals

Overview

Sorting arranges elements in order. It is rarely the final answer to an interview problem, but it is very often the first step: sorting enables binary search, two pointers, greedy choices, merging intervals, and grouping duplicates.

You should know how the classic algorithms work, their complexity, and whether they are stable and in-place. In practice you call the built-in sort (Timsort for objects in Java and in V8's JavaScript; dual-pivot quicksort for Java primitives) and supply the right comparator.

When to use it

• Order unlocks a faster technique: binary search, two pointers, or greedy.
• You need to group equal elements together or detect duplicates.
• Intervals, events, or meetings must be processed in time order.
• Values are small integers in a known range: counting sort gives O(n + k).

Problem patterns it solves

Where it is used in real software

Key terms

Stable sort

Equal elements keep their original relative order. Needed when sorting by multiple keys in passes.

In-place

Uses O(1) or O(log n) extra memory.

Comparison sort lower bound

Any sort that only compares elements needs Omega(n log n) comparisons in the worst case.

Comparator

A function (a, b) that returns negative if a comes first, positive if b comes first, 0 if equal.

Pivot

The element quicksort partitions around.

The main algorithms

1. 1
   Bubble sort: O(n^2), stable

   Repeatedly swap adjacent out-of-order elements; the largest bubbles to the end each pass. Mostly educational.

2. 2
   Selection sort: O(n^2), not stable

   Find the minimum of the unsorted part and swap it into place. Makes only O(n) swaps.

3. 3
   Insertion sort: O(n^2), stable, O(n) if nearly sorted

   Insert each element into the sorted prefix by shifting larger elements right. Excellent for small or nearly sorted arrays.

4. 4
   Merge sort: O(n log n), stable, O(n) space

   Split in half, sort each half recursively, merge two sorted halves with two pointers.

5. 5
   Quicksort: O(n log n) average, O(n^2) worst, in-place

   Partition around a pivot so smaller elements go left and larger go right, then recurse on each side. Random pivots avoid the worst case.

6. 6
   Heap sort: O(n log n), in-place, not stable

   Build a max-heap, then repeatedly move the maximum to the end.

7. 7
   Counting sort: O(n + k), stable

   Count occurrences of each value in range k, then write them back in order. Not comparison-based.

Comparing sorting algorithms

n elements; k = range of values for counting sort

Merge sort guarantees O(n log n) and stability at the cost of memory. Quicksort is usually fastest in practice. Heap sort is in-place with guaranteed O(n log n). Counting sort breaks the n log n barrier when values are small integers.

Implementation

1function insertionSort(arr) {2  for (let i = 1; i < arr.length; i++) {3    const current = arr[i];4    let j = i - 1;5    while (j >= 0 && arr[j] > current) {6      arr[j + 1] = arr[j]; // shift right7      j--;8    }9    arr[j + 1] = current;10  }11  return arr;12}13 14function mergeSort(arr) {15  if (arr.length <= 1) return arr;16  const mid = Math.floor(arr.length / 2);17  const left = mergeSort(arr.slice(0, mid));18  const right = mergeSort(arr.slice(mid));19 20  const merged = [];21  let i = 0, j = 0;22  while (i < left.length && j < right.length) {23    merged.push(left[i] <= right[j] ? left[i++] : right[j++]); // <= keeps it stable24  }25  return merged.concat(left.slice(i), right.slice(j));26}27 28function quickSort(arr, low = 0, high = arr.length - 1) {29  if (low >= high) return arr;30  const pivotIndex = low + Math.floor(Math.random() * (high - low + 1));31  [arr[pivotIndex], arr[high]] = [arr[high], arr[pivotIndex]];32  const pivot = arr[high];33  let i = low;34  for (let j = low; j < high; j++) {35    if (arr[j] < pivot) {36      [arr[i], arr[j]] = [arr[j], arr[i]];37      i++;38    }39  }40  [arr[i], arr[high]] = [arr[high], arr[i]];41  quickSort(arr, low, i - 1);42  quickSort(arr, i + 1, high);43  return arr;44}45 46// Built-in: ALWAYS pass a comparator for numbers47[10, 9, 1].sort();               // [1, 10, 9]  (string comparison!)48[10, 9, 1].sort((a, b) => a - b); // [1, 9, 10]49 50// Multi-key: by age ascending, then name51const people = [{ name: "Bo", age: 30 }, { name: "Al", age: 30 }, { name: "Cy", age: 25 }];52people.sort((a, b) => a.age - b.age || a.name.localeCompare(b.name)); // Cy, Al, Bo

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Sorting numbers in JavaScript without a comparator.

  Fix: Always use arr.sort((a, b) => a - b).

• Comparator a - b that overflows in Java.

  Fix: Use Integer.compare(a, b) for values that may be large or negative.

• Inconsistent comparator.

  Fix: It must be transitive and return 0 for equal elements, or sorting can throw or misbehave.

• Sorting when O(n) is required.

  Fix: Check constraints; counting sort, bucket sort, or a hash map may be expected.

Interview questions

Practice problems