Sorting algorithms

In plain English

Complexity measures how much work an algorithm does as the input grows, and Big O notation writes this as O(n²), meaning the work grows with the square of the input, or O(n log n), meaning it grows just a bit faster than linear. Insertion sort takes each element and slides it backward into place, which is simple but slow on large lists. Merge sort splits the list in half, sorts each half, and merges them back together for reliable O(n log n) work. Quicksort picks a pivot and partitions the list into smaller and larger groups before sorting each side. Stability means equal elements keep their original order, which matters when sorting by several keys one after another, and in practice JavaScript built-in sort is the right tool rather than writing your own.

Step by step

1. 1Trace insertion sort on [5, 2, 9, 1] by sliding each element into place.
2. 2Split a list in half and describe what merge sort does to each half.
3. 3Run both sorts and the built-in sort on the same numbers.
4. 4Check that equal values keep their order in insertion and merge sort.

function insertionSort(values) {
  const items = [...values]
  for (let i = 1; i < items.length; i++) {
    const current = items[i]
    let j = i - 1
    while (j >= 0 && items[j] > current) {
      items[j + 1] = items[j]
      j--
    }
    items[j + 1] = current
  }
  return items
}

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 i = 0
  let 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))
}

const numbers = [5, 2, 9, 1, 5, 6]
console.log(insertionSort(numbers))
console.log(mergeSort(numbers))
console.log(numbers.sort((a, b) => a - b))

Common mistakes

• Calling sort() on numbers without a comparator sorts them as strings, so 10 sorts before 2.
• Confusing stable and unstable sorts is easy, but stability only matters when you sort by several keys in order.
• Assuming insertion sort is fast for large lists is wrong, because its O(n²) work grows quickly with the input size.
• Writing your own quicksort for production is usually a mistake, because the built-in sort is already tested and fast.