Skip to content

Sorting Algorithms Deep Dive

Implement bubble, insertion, merge, and quick sort; understand their stability, complexity, and trade-offs.

What you'll learn

  • Comparison-based sorts and the O(n log n) lower bound
  • Stable vs unstable sorting
  • In-place vs out-of-place sorting
  • When to use each sorting algorithm

Concept

Sorting Algorithms Deep Dive

Sorting arranges elements in order. It is one of the most studied problems in computer science because so many other algorithms depend on sorted data.

The O(n log n) Barrier

Any comparison-based sort needs at least Omega(n log n) comparisons in the worst case. This is because there are n! possible orderings, and each comparison distinguishes between 2 cases, so you need at least log2(n!) approx n log n comparisons. To beat this barrier, you must use non-comparison sorts (counting sort, radix sort) that exploit data structure.

Stability

A sort is stable if equal elements retain their original relative order. Merge sort and insertion sort are stable; quick sort and heap sort are not. Stability matters when sorting by a secondary key.

Major Algorithms

Bubble sort is O(n^2), simple but slow. Insertion sort is O(n^2) worst, O(n) best for nearly sorted data. Merge sort is O(n log n) guaranteed, stable, but O(n) extra space. Quick sort is O(n log n) average, O(n^2) worst, in-place, fastest in practice due to cache efficiency.

Real-World Choice

Most language standard libraries use a hybrid: Timsort (merge + insertion) in Python/Java, introsort (quick + heap + insertion) in C++.

Example

              // Insertion sort - O(n^2) worst, O(n) best, stable, in-place
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
    arr[j + 1] = key;
  }
  return arr;
}
// Merge sort - O(n log n) guaranteed, stable
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  const merged = [];
  let i = 0, 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.concat(left.slice(i), right.slice(j));
}
console.log(insertionSort([5, 2, 8, 1, 9, 3]));
console.log(mergeSort([5, 2, 8, 1, 9, 3]));
            

Insertion sort builds the sorted array one element at a time. Merge sort divides the array, recursively sorts halves, then merges them in order.

Try it

  • Case Converter

    Sorting and case conversion both transform ordered data - see how stable transforms preserve structure.

Common mistakes

The mistake

Expecting quick sort to always be O(n log n).

The fix

Quick sort is O(n^2) in the worst case (e.g., already sorted data with a naive pivot). Use random pivot or median-of-three.

The mistake

Ignoring stability when sorting by multiple keys.

The fix

If you sort by a secondary key after a primary key sort, the second sort must be stable to preserve the primary order for equal secondary keys.

Look up unfamiliar terms

A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.

View glossary

Build real projects

Apply what you learned by building guided projects with starter code and solutions.

View projects

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors