Big O notation · part 3 of 8

Why sorting is O(n log n)

16 June 2026

Let's chat about where log n comes from first. Our menu is printed in alphabetical order. You want to find "Pistachio". You don't read from the top: you open it in the middle, see whether you've landed before or after Pistachio, and throw away the half that can't contain it. Then you do the same to what's left. Every single step halves the search. Sound familiar?

// Binary search
function findFlavour(menuItems, targetFlavour) {
  let left = 0;
  let right = menuItems.length - 1;

  while (left <= right) {
    const middle = Math.floor((left + right) / 2);
    const currentFlavour = menuItems[middle];

    if (currentFlavour === targetFlavour) return middle;

    if (currentFlavour < targetFlavour) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }

  return -1;
}

The number of times you can halve n before you're down to one item is log₂ n, so this is O(log n). And that's why log n barely moved on the grapher: a thousand items is about ten steps, a million items is about twenty. Double the size of the menu and you pay one extra step. One. That's why sorted data is so beautiful.

n log n

Now we can explain the sort from the last section. A good comparison sort works by divide and conquer: split the list in half, sort each half, merge them back. The splitting goes log n levels deep (halving again), and stitching things back together does about n work at each level. n work, log n times, is O(n log n).

The practical takeaway is simpler than the maths: any time you catch yourself saying "I'll just sort it first", you've spent O(n log n). Often that's a bargain, because what it buys you is cheap (like an O(n) neighbour-scan).