Sorting Algorithms Pattern

Why this pattern matters for LeetCode

Sorting is the unlock for dozens of other patterns. Two Pointers needs a sorted array. Binary Search needs a sorted array. Many greedy interval problems need intervals sorted by start or end time. Bubble sort and insertion sort are O(n²) and time out on large inputs. Merge sort and quicksort are O(n log n) — the fastest any comparison-based sort can be. Knowing which algorithm to use and why is as important as implementing one.

What the Sorting Algorithms pattern is

Sorting algorithms rearrange an array into a defined order. Comparison-based sorts are bounded by O(n log n) at best. Merge sort always achieves O(n log n) by splitting and merging. Quicksort achieves O(n log n) on average via partitioning but degrades to O(n²) in the worst case. Insertion sort is O(n²) in general but O(n) on nearly-sorted data. JavaScript's built-in Array.sort() uses Timsort (merge sort + insertion sort hybrid) and is O(n log n) stable.

Reach for Sorting Algorithms when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Sorting Algorithms

• ✓Merge sort: when O(n log n) guaranteed time is needed and O(n) auxiliary space is acceptable
• ✓Quicksort: when O(n log n) average time with O(log n) space is needed (in-place)
• ✓Insertion sort: when the input is nearly sorted (O(n) best case) or for small arrays
• ✓Array.sort(): for all other practical sorting in JavaScript interviews — it's O(n log n) stable
• ✓Counting/Bucket sort: when values are bounded integers in a small range (O(n + k))

When NOT to use Sorting Algorithms

• ✕The input is already sorted — sorting it again wastes time
• ✕You only need the maximum or minimum — a single O(n) linear scan is faster than sorting
• ✕You need the k-th element — a heap or quickselect is O(n) or O(n log k), faster than full sort
• ✕Values are unbounded strings and a custom comparator is complex — be careful about comparator correctness

Better alternative: If you only need one extreme, use a linear scan or heap. If you need the k-th element, use quickselect or a heap of size k.

JavaScript code template

Merge sort and quicksort implementations

// Merge sort — O(n log n) guaranteed, O(n) space, stable
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));
  return merge(left, right);
}
function merge(l, r) {
  const out = [];
  let i = 0, j = 0;
  while (i < l.length && j < r.length) {
    out.push(l[i] <= r[j] ? l[i++] : r[j++]);
  }
  return out.concat(l.slice(i), r.slice(j));
}

// Quicksort — O(n log n) average, O(n²) worst, O(log n) space, unstable
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  const p = partition(arr, lo, hi);
  quickSort(arr, lo, p - 1);
  quickSort(arr, p + 1, hi);
}
function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) [arr[i++], arr[j]] = [arr[j], arr[i]];
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

Merge sort splits at the midpoint, sorts each half recursively, and merges. Guaranteed O(n log n). Quicksort picks a pivot (last element here), partitions: elements ≤ pivot go left, elements > pivot go right. The pivot lands in its final sorted position. Recurse on each side. Average O(n log n) but degrades to O(n²) on already-sorted input with this pivot choice — use a random pivot in practice.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Ask: does the problem need a full sort, or just the max, min, or k-th element?
2. 2If sorting: use Array.sort() in JavaScript for most interview problems (it's O(n log n) stable).
3. 3If you must implement: choose merge sort for guaranteed O(n log n) and stability, quicksort for in-place O(log n) space.
4. 4Write the comparator carefully for non-numeric data — a - b for ascending numbers, (a, b) => a.localeCompare(b) for strings.
5. 5Remember sorting is often a preprocessing step that enables another pattern (two pointers, binary search, greedy).

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Squares of a Sorted Array

  Sort the squared values — or use two pointers on the original sorted array to avoid re-sorting.

  Premium→
• Top K Frequent Elements

  Frequency map + sort by count, or bucket sort by frequency for O(n) time.

  Premium→

Coming soon

• Sort an Array

  Implement merge sort or quicksort from scratch — the canonical sorting algorithm problem.

  Coming soon
• Merge Intervals

  Sort intervals by start time first — then a linear scan detects overlaps and merges them.

  Coming soon

Common mistakes beginners make

• ✕Using the default Array.sort() on numbers without a comparator — JavaScript sorts lexicographically by default, so [10, 2, 1].sort() gives [1, 10, 2]. Always pass (a, b) => a - b for ascending numeric sort.
• ✕Choosing bubble sort or selection sort (O(n²)) for large inputs — they time out. Use merge sort or quicksort for O(n log n).
• ✕Forgetting that quicksort can degrade to O(n²) on sorted input when always picking the last/first element as pivot — randomize the pivot or use the median-of-three heuristic.
• ✕Assuming sort is stable when it isn't — quicksort is not stable (equal elements can swap order). Use merge sort when relative order of equals matters.

Merge Sort vs Quicksort vs Insertion Sort

Choose the right tool for the job.

Time and space complexity

The O(n log n) lower bound for comparison-based sorting is proven: any comparison sort must make at least log₂(n!) comparisons, which by Stirling's approximation is Ω(n log n). Merge sort achieves this exactly. Quicksort achieves O(n log n) on average (random pivot); its worst case is O(n²) when the pivot is always the smallest or largest element. Insertion sort is O(n) when the input is already sorted (zero swaps needed).

Frequently asked questions

Why does JavaScript's Array.sort() sort numbers wrong without a comparator?

By default, Array.sort() converts elements to strings and sorts them lexicographically. '10' comes before '2' because '1' < '2'. For numeric sort always pass a comparator: arr.sort((a, b) => a - b) for ascending. This is one of the most common bugs in JavaScript interview code.

Is merge sort or quicksort better for interviews?

Merge sort is safer: guaranteed O(n log n), stable, and the implementation is clean. Quicksort is O(n log n) average but O(n²) worst case (though randomized pivot makes worst case astronomically unlikely). For interviews, implement merge sort if asked to implement a sort. If space is the concern, mention quicksort's O(log n) call stack vs merge sort's O(n) auxiliary arrays.

When should I reach for sort instead of a heap?

Sort when you need the full ordering of all elements. Heap when you only need the top K elements — a heap of size K gives O(n log k) which beats O(n log n) full sort when k << n. If you need to repeatedly query the maximum as elements are added and removed, a heap wins. If you sort once and query many times, sort wins.

What is a stable sort and when does it matter?

A stable sort preserves the relative order of elements with equal keys. If two elements have the same value, their original order is unchanged after the sort. Merge sort is stable; quicksort is not. Stability matters when you sort by one key and then by another — the second sort should preserve the order from the first. JavaScript's Array.sort() is guaranteed stable as of ES2019.