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.

In day-to-day development, you almost never implement a sort yourself. JavaScript gives you Array.prototype.sort, databases give you ORDER BY, and most frameworks wrap one or the other. That is the right default: those implementations are fast, well tested, and maintained by people who optimise for edge cases you will never hit in application code.

The reason to learn how sorting works is not to rewrite what the runtime already does. It is so you can recognise what is happening when performance matters, choose the right tool for the job, and avoid patterns that fight the algorithm underneath. Nearly-sorted data, stable ordering, memory limits, and guaranteed worst-case behaviour all point to different choices. You do not need to implement merge sort by hand; you do need to know when merge sort is the better fit than quicksort.

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

You do not need to implement any of this yourself. In production, reach for the built-in sort, a database index, or a library that already solved the problem. Array.prototype.sort in JavaScript delegates to a highly tuned native implementation, often a hybrid like Timsort that blends ideas from merge sort and insertion sort. That is almost always the correct answer for application code.

What this post gives you is a mental model. When a sort feels slow, you can ask whether the data is nearly sorted, whether you need stable ordering, or whether you are sorting on disk rather than in memory. When you are designing a system, you can reason about whether O(n log n) is acceptable or whether a different data structure avoids sorting altogether. When an interviewer asks you to compare algorithms, you can explain trade-offs with something concrete behind the words.

The goal is not to leave here ready to paste bubble sort into a pull request. It is to understand what your tools are doing so you can trust them, spot when they are the wrong fit, and make better decisions without reinventing forty years of computer science.