Skip to content
Lydia Hallie theavocoder
Newsletter
Algorithms / Sorting

Sorting Algorithms

Learn about sorting algorithms, how they work, their implementation, and their runtimes.

Compare quadratic runtimes See logarithmic time

Four sorts, four tradeoffs

Sorting is a useful way to study algorithms because the problem is easy to state and the tradeoffs are easy to see. The right choice depends on the size of the data, how much of it is already ordered, and whether you can afford extra memory.

Bubble sort

Bubble sort repeatedly compares adjacent values and swaps them when they are out of order. It is simple to read and quadratic in the average and worst case, which makes it a teaching tool rather than a production choice.

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

Insertion sort

Insertion sort walks through the list and inserts each value into the sorted part behind it. It is quadratic in the worst case, but it is fast on small or nearly sorted inputs. That is why some engines switch to it for small ranges.

Merge sort

Merge sort divides the list in half, sorts each half, and merges the results. It runs in linearithmic time, written O(n log n), and it is stable. The tradeoff is the extra memory used during the merge.

function merge(left, right) {
  const result = [];
  while (left.length && right.length) {
    result.push(left[0] <= right[0] ? left.shift() : right.shift());
  }
  return [...result, ...left, ...right];
}

Quick sort

Quick sort chooses a pivot, partitions the values around it, and recurses. It is fast in practice and usually runs in linearithmic time, but its worst case is quadratic when the pivot choices are poor. Randomized or median pivots make that case unlikely.

What to take away

Big O tells you how the work grows, not which sort is always best. For small arrays, a simple algorithm can beat a clever one. For large arrays, the difference between quadratic and linearithmic is the difference between usable and unusable. The Big O guide is the map for those decisions.

References and further reading