Sorting

How It Works

Sorting rearranges a collection into a defined order (ascending, descending, or by a custom comparator) so that relationships between elements (equal, adjacent, closest) become positional and therefore cheap to discover. Once data is sorted, problems that would otherwise require checking every pair (O(n²)) often reduce to a single linear scan (O(n)) or a binary search (O(log n)).

Comparison-based sorting algorithms fall into a few families. Divide-and-conquer sorts like merge sort and quicksort split the array, sort the pieces (often recursively), and combine them: merge sort by merging two sorted halves in linear time, quicksort by partitioning around a pivot so everything smaller ends up to its left and everything larger to its right. Simple quadratic sorts (bubble, insertion, selection) repeatedly scan and swap, and are O(n²) but easy to reason about and genuinely fast on small or nearly-sorted inputs. Comparison sorts are provably bounded below by O(n log n) in the average/worst case, which is why merge sort, quicksort, and heapsort all converge on that bound. Non-comparison sorts (counting sort, radix sort) sidestep that bound entirely by exploiting structure in the data (e.g. small integer ranges), achieving O(n + k) instead.

When To Use It

The clearest signal is that the problem becomes easier, sometimes trivial, if the input were ordered. "Find if two numbers sum to a target," "find the closest pair of points on a line," or "group anagrams" all become simpler once you can rely on adjacency or monotonic order.

Sorting is also the standard first step for finding duplicates or groups of equal elements, since equal elements become adjacent after sorting, turning an O(n²) all-pairs comparison into an O(n) linear scan after the O(n log n) sort.

Greedy algorithms frequently depend on processing items in a specific order: interval scheduling (sort by end time), task scheduling (sort by deadline or duration), or fractional knapsack (sort by value-to-weight ratio) all require a sort as a setup step before the greedy choice logic runs.

Finally, if you need the k-th smallest/largest element, a running median, or repeated access to "the next smallest remaining item," sorting up front (or maintaining a sorted structure, like a heap) is usually the cleanest path, though for a single k-th-element query, a partial sort (quickselect) can do better than a full sort.

Time & Space Complexity

Merge sort guarantees O(n log n) time in all cases (best, average, worst) because it always splits evenly and merges in linear time, but it costs O(n) auxiliary space for the temporary arrays used during merging; it is not in-place. Quicksort also averages O(n log n), typically with better constant factors and O(log n) space (the recursion stack) since partitioning happens in place, but a poor pivot choice degrades it to O(n²) worst case (e.g. always picking the first element on an already-sorted array). Heapsort guarantees O(n log n) time with O(1) extra space, trading a bit of speed and cache-friendliness for that space guarantee. The simple quadratic sorts are O(n²) in general but insertion sort drops to nearly O(n) on already-sorted or nearly-sorted data, which is why hybrid sorts (like Timsort, used internally by many language runtimes) fall back to insertion sort for small partitions.

// Merge sort: divide-and-conquer, O(n log n) time, O(n) space
function mergeSort(arr) {
  if (arr.length <= 1) return arr; // base case

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

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

  // Append whatever remains; only one of these has leftover elements
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);

  return result;
}

mergeSort([5, 2, 9, 1, 5, 6]); // [1, 2, 5, 5, 6, 9]

Alternative Approaches

For most real-world code, Array.prototype.sort() (with an explicit comparator, since the default sort is lexicographic and will sort [10, 2] as [10, 2] incorrectly by numeric expectation) is the right call; modern engines use a hybrid, highly-optimized algorithm (V8 uses Timsort-like approaches) that beats a hand-rolled sort in practice. Hand-rolling merge sort, quicksort, or heapsort is primarily an interview exercise to demonstrate understanding of divide-and-conquer, partitioning, and complexity tradeoffs, or is needed when you require a guarantee the built-in doesn't give you: e.g., strict O(1) space (heapsort) or true worst-case O(n log n) (merge sort, since naive quicksort degrades on adversarial input).

When the data has known structure (small integer ranges, fixed-length strings), non-comparison sorts like counting sort or radix sort can beat the O(n log n) comparison-sort floor entirely, running in O(n + k) time.

Common Mistakes

• Using the default Array.prototype.sort() without a comparator on numbers: it sorts elements as strings by default, so [10, 2, 1].sort() gives [1, 10, 2], not [1, 2, 10].
• Assuming a sort is stable when it isn't: stability (equal elements keep their relative order) matters when sorting by a secondary key or objects with tie-breaking logic; check the guarantee for the language/engine rather than assuming.
• Off-by-one errors in partition/merge indices: a classic quicksort or merge sort bug, e.g. using <= instead of < in a merge loop and reading past the array bounds.
• Picking a bad quicksort pivot: always choosing the first or last element degrades quicksort to O(n²) on sorted or reverse-sorted input; randomizing or using median-of-three mitigates this.
• Forgetting that slice()-based merge sort allocates new arrays at every level: correct, but worth knowing it's not in-place, since interviewers may ask you to reduce space usage.
• Sorting when a linear-time approach (hashing, counting) would suffice: reaching for a sort out of habit when the problem's constraints (small integer range, need for O(n)) suggest a faster non-comparison approach.

Pattern Summary

Sorting trades an upfront O(n log n) cost for turning otherwise quadratic pairwise problems into linear scans, binary searches, or straightforward greedy passes. The key interview skill isn't memorizing every sort's code; it's recognizing when ordering the input unlocks a simpler algorithm, and being able to reason about the time/space/stability tradeoffs between the standard O(n log n) options.