Sorting Algorithms Explained

Sorting is one of the first places computer science stops feeling abstract. You have a list of values in the wrong order; you need them in the right order; and the difference between a naive approach and a good one is the difference between a UI that feels instant and one that stalls on large inputs.

This post walks through six common sorting algorithms. Each section includes an animated demo, an explanation of how the sort works, its strengths and weaknesses, and a speed rating. Every demo uses the same shuffled set of 20 bars so you can compare behaviour on equal footing.

The table above is the cheat sheet. The sections below show what those numbers feel like in practice.

Bubble sort

Bubble sort walks the array repeatedly, comparing each adjacent pair and swapping them when the left bar is taller than the right. After each full pass, the tallest unsorted bar has "bubbled" to its correct position at the end.

function bubbleSort(values) {  const array = [...values];
  for (let pass = 0; pass < array.length - 1; pass += 1) {    for (let index = 0; index < array.length - pass - 1; index += 1) {      if (array[index] > array[index + 1]) {        [array[index], array[index + 1]] = [array[index + 1], array[index]];      }    }  }
  return array;}

How it works: Compare neighbours, swap when out of order, repeat until no swaps are needed. Simple, local, and easy to reason about.

Pluses: Minimal extra memory (O(1)), stable (equal values keep their relative order), and very easy to implement or teach.

Minuses: Slow on large lists. Average and worst case are O(n²). Even with early-exit optimisations, it is rarely the right choice in production.

Best for: Teaching, tiny datasets, or situations where clarity matters more than speed.

Selection sort

Selection sort divides the array into a sorted prefix and an unsorted suffix. Each pass scans the unsorted section for the smallest bar and swaps it into the next open slot at the front.

function selectionSort(values) {  const array = [...values];
  for (let index = 0; index < array.length - 1; index += 1) {    let minIndex = index;
    for (let scan = index + 1; scan < array.length; scan += 1) {      if (array[scan] < array[minIndex]) {        minIndex = scan;      }    }
    if (minIndex !== index) {      [array[index], array[minIndex]] = [array[minIndex], array[index]];    }  }
  return array;}

How it works: Find the minimum, swap it into place, shrink the unsorted region by one, repeat.

Pluses: O(1) extra space and at most n - 1 swaps, useful when writes are expensive (e.g. flash memory).

Minuses: Always O(n²) comparisons, even on already-sorted input. Not stable unless you add extra bookkeeping.

Best for: Small arrays where swap cost dominates, or as a teaching contrast to insertion sort.

Insertion sort

Insertion sort builds a sorted section from the left, one bar at a time. It takes the next bar, shifts larger neighbours to the right, and slides the bar into the gap, the same idea as sorting a hand of playing cards.

function insertionSort(values) {  const array = [...values];
  for (let index = 1; index < array.length; index += 1) {    const value = array[index];    let hole = index;
    while (hole > 0 && array[hole - 1] > value) {      array[hole] = array[hole - 1];      hole -= 1;    }
    array[hole] = value;  }
  return array;}

How it works: Maintain a sorted prefix. Insert each new element into its correct position by shifting larger values right.

Pluses: Fast on small or nearly-sorted data (O(n) best case), stable, in-place, and excellent as the inner sort in hybrid algorithms like Timsort.

Minuses: O(n²) average and worst case, which is painful on large random inputs.

Best for: Small arrays, nearly-sorted data, and as a building block inside industrial-grade sorts.

Merge sort

Merge sort is divide-and-conquer: split the array in half, sort each half recursively, then merge the two sorted halves into one sorted run. The merge step is where the work happens, repeatedly taking the smaller front element from either half.

function mergeSort(values) {  if (values.length <= 1) {    return values;  }
  const mid = Math.floor(values.length / 2);  const left = mergeSort(values.slice(0, mid));  const right = mergeSort(values.slice(mid));
  return merge(left, right);}
function merge(left, right) {  const result = [];  let leftIndex = 0;  let rightIndex = 0;
  while (leftIndex < left.length && rightIndex < right.length) {    if (left[leftIndex] <= right[rightIndex]) {      result.push(left[leftIndex]);      leftIndex += 1;    } else {      result.push(right[rightIndex]);      rightIndex += 1;    }  }
  return result.concat(left.slice(leftIndex), right.slice(rightIndex));}

How it works: Split, sort recursively, merge sorted halves. Predictable O(n log n) regardless of input shape.

Pluses: Guaranteed O(n log n) worst case, stable, and parallelises well. The go-to choice when consistent performance matters.

Minuses: Needs O(n) extra space for the merge buffer (unless you implement an in-place variant, which is trickier).

Best for: Large datasets, external sorting (data on disk), linked lists, and anywhere stable O(n log n) is required.

Quick sort

Quicksort picks a pivot, partitions the array so everything smaller sits left and everything larger sits right, then recurses on each side. In practice it is often the fastest general-purpose in-memory sort, but the pivot choice matters.

function quickSort(values, left = 0, right = values.length - 1) {  if (left >= right) {    return values;  }
  const pivotIndex = partition(values, left, right);  quickSort(values, left, pivotIndex - 1);  quickSort(values, pivotIndex + 1, right);
  return values;}
function partition(values, left, right) {  const pivotValue = values[right];  let storeIndex = left;
  for (let index = left; index < right; index += 1) {    if (values[index] < pivotValue) {      [values[index], values[storeIndex]] = [values[storeIndex], values[index]];      storeIndex += 1;    }  }
  [values[storeIndex], values[right]] = [values[right], values[storeIndex]];  return storeIndex;}

How it works: Partition around a pivot, recurse on sub-arrays. Average case O(n log n) with very low constant factors.

Pluses: Fast in practice, in-place (O(log n) stack space), and cache-friendly when implemented well.

Minuses: O(n²) worst case on adversarial or unlucky pivots. Not stable by default. Many production implementations switch to insertion sort for small sub-arrays.

Best for: General-purpose in-memory sorting. It is what most standard libraries use (often with median-of-three or random pivot improvements).

Heap sort

Heap sort treats the array as a binary max-heap. It builds the heap, repeatedly extracts the maximum to the end of the array, and sifts the root back down to restore the heap property.

function heapSort(values) {  const array = [...values];  const length = array.length;
  for (let start = Math.floor(length / 2) - 1; start >= 0; start -= 1) {    siftDown(array, start, length - 1);  }
  for (let end = length - 1; end > 0; end -= 1) {    [array[0], array[end]] = [array[end], array[0]];    siftDown(array, 0, end - 1);  }
  return array;}

How it works: Build a max-heap, swap the root (max) to the tail, shrink the heap, sift down, repeat.

Pluses: Guaranteed O(n log n) worst case, O(1) extra space, and no worst-case quadratic surprise like naive quicksort.

Minuses: Slower than well-tuned quicksort in practice due to poorer cache locality. Not stable.

Best for: Memory-constrained environments where guaranteed O(n log n) is required and stability does not matter.

Choosing a sort in practice

Modern runtimes do not expect you to hand-roll sorts for production code. Array.prototype.sort in JavaScript uses highly tuned native implementations. The value of knowing these algorithms is understanding why your code scales or stalls, how to pick structures and patterns wisely, and how to reason about time complexity in interviews and system design.