Sorting Algorithms Explained

Introduction

Every language ships with a built-in sort function, so why do sorting algorithms remain such a permanent fixture of technical interviews and computer science courses? Because sorting is one of the clearest windows into complexity analysis, recursion, and algorithmic trade-offs. This guide walks through the sorting algorithms worth understanding deeply: bubble sort as a baseline, and merge sort and quicksort as the two divide-and-conquer algorithms that actually matter in practice.

Bubble Sort: The Simple Baseline

Bubble sort repeatedly steps through the array, swapping adjacent elements that are out of order, until no swaps are needed:

function bubbleSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length - 1; i++) {
    for (let j = 0; j < a.length - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
      }
    }
  }
  return a;
}

console.log(bubbleSort([5, 2, 9, 1, 5, 6])); // [1, 2, 5, 5, 6, 9]

Bubble sort runs in O(n²) time in the worst and average case, which makes it impractical for large inputs. Its value is purely educational: it is the simplest possible sort to trace by hand and understand completely.

Merge Sort: Divide, Sort, Combine

Merge sort recursively splits the array in half until each piece has one element, then merges sorted pieces back together:

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(left, right) {
  const result = [];
  let i = 0, j = 0;

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

  return result.concat(left.slice(i)).concat(right.slice(j));
}

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

Merge sort guarantees O(n log n) time in every case — best, average, and worst — because the split is always exactly in half regardless of the input's initial order. The trade-off is O(n) extra memory for the temporary arrays created during merging, and it is naturally stable, preserving the relative order of equal elements.

Quicksort: Partition Around a Pivot

Quicksort picks a pivot element, partitions the array so smaller elements come before it and larger elements come after, then recursively sorts each partition:

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const [pivot, ...rest] = arr;
  const left = rest.filter((n) => n < pivot);
  const right = rest.filter((n) => n >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([5, 2, 9, 1, 5, 6])); // [1, 2, 5, 5, 6, 9]

This simple version is easy to read but not memory-efficient because filter creates new arrays; production implementations partition in place using swaps, using only O(log n) extra space for the recursion stack. Quicksort averages O(n log n) time, matching merge sort, but its worst case is O(n²) — specifically when the chosen pivot repeatedly turns out to be the smallest or largest remaining element, such as when sorting an already-sorted array with a naive "always pick the first element" pivot strategy.

Comparing the Algorithms

Algorithm    | Best        | Average     | Worst       | Space    | Stable?
--------------|-------------|-------------|-------------|----------|--------
Bubble Sort   | O(n)        | O(n^2)      | O(n^2)      | O(1)     | Yes
Merge Sort    | O(n log n)  | O(n log n)  | O(n log n)  | O(n)     | Yes
Quicksort     | O(n log n)  | O(n log n)  | O(n^2)      | O(log n) | No*

* can be made stable with extra bookkeeping, but typical implementations are not

Merge sort's guaranteed worst case makes it attractive when predictable performance matters (and when extra memory is acceptable); quicksort's lower memory footprint and excellent average-case performance make it a common default for general-purpose in-memory sorting, especially with randomized or median-of-three pivot selection to avoid its worst case in practice.

Why Built-in Sorts Are (Usually) Hybrids

Most real-world sort implementations, like Python's Timsort or V8's TimSort-based Array.prototype.sort, are hybrids: they use insertion sort for small subarrays (where its low overhead wins despite O(n²) complexity) and a divide-and-conquer algorithm for larger ones, sometimes switching strategies again based on how "sorted" the input already appears to be.

Best Practices

• Use your language's built-in sort for real applications; hand-rolled sorting algorithms are almost never faster or safer in production.
• Understand time and space complexity trade-offs well enough to explain them clearly in an interview setting.
• Know which common sorts are stable, since stability matters whenever you sort by one key but want to preserve relative order on ties.
• Practice tracing through merge sort and quicksort by hand on a small example — this is usually more valuable than memorizing the code.

Common Mistakes to Avoid

• Assuming quicksort always outperforms merge sort — its O(n²) worst case is real and can happen with poor pivot choices on adversarial or already-sorted input.
• Forgetting that a naive recursive quicksort or mergesort implementation (like the ones shown for clarity here) uses more memory than an in-place, production-grade version.
• Confusing "average case" with "guaranteed case" when comparing algorithms — quicksort's average is excellent, but its worst case is real.
• Not considering stability when it actually matters for the problem at hand, such as sorting a list of objects by one field while needing ties to stay in their original relative order.

Where Quicksort's Worst Case Comes From

Quicksort's average-case O(n log n) performance is excellent, but understanding exactly when it degrades to its O(n²) worst case is what separates a naive implementation from a production-ready one. The worst case happens when the chosen pivot is consistently the smallest or largest remaining element, which turns each partition step into removing just one element instead of roughly splitting the array in half:

function quicksort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quicksort(arr, low, pivotIndex - 1);
    quicksort(arr, pivotIndex + 1, high);
  }
  return arr;
}

Always picking the first or last element as the pivot is the classic mistake that triggers this worst case — on an already-sorted or reverse-sorted array (a surprisingly common real-world input), that pivot choice is always the extreme value, and the algorithm degenerates into something resembling selection sort, with quadratic time and linear recursion depth. The standard fix is choosing a pivot less predictably: a random index, or the median of the first, middle, and last elements ("median-of-three"), both of which make it statistically very unlikely that an adversarial or already-sorted input repeatedly hits the worst case. This is exactly why most production sorting libraries either use a randomized pivot or switch to a completely different algorithm (like introsort, which falls back to heapsort if recursion gets too deep) rather than trusting a naive pivot choice.

Conclusion

Sorting algorithms are a compact case study in algorithmic trade-offs: bubble sort trades performance for simplicity, merge sort trades memory for guaranteed worst-case performance, and quicksort trades worst-case guarantees for excellent average-case speed and low memory use. Understanding these trade-offs — not just memorizing the code — is what carries over to evaluating any algorithm you encounter afterward.