Understanding Big-O by Timing Four Sorting Algorithms on the Same Data

Big-O notation made sense as a definition long before it made sense as something that mattered. O(n²) grows faster than O(n log n) — fine, understood, and also completely abstract until the day a report that should have taken seconds instead ran for four minutes because of a nested loop sorting a list that had quietly grown from 200 rows to 40,000. What actually made the difference between "the sorting algorithm is O(n²)" as a fact to recite and as something felt was timing four of them, on the same growing arrays, and watching the curves diverge with my own eyes.

The setup: same data, four algorithms, honest timing

The test used randomly generated integer arrays at five sizes — 100, 1,000, 5,000, 10,000, and 20,000 elements — with the exact same array (by seed) fed to all four algorithms at each size, so no algorithm got an easier or harder input than another. Each run was timed five times and averaged, using microtime(true) before and after the sort, on a plain PHP implementation of each algorithm rather than a built-in sort function, specifically so the comparison reflected the algorithm's actual behavior rather than a language's internal optimizations.

function timeSort(callable $sortFn, array $data): float {
    $copy = $data; // never sort the original — every algorithm needs a fresh unsorted array
    $start = microtime(true);
    $sortFn($copy);
    return microtime(true) - $start;
}

That one-line comment matters more than it looks: the first version of this test accidentally passed the same array by reference across algorithms, so later algorithms were "sorting" an array that earlier ones had already sorted — a bug that produced suspiciously fast results for whichever algorithm ran last, and a good early reminder that a benchmark is only as trustworthy as the setup around it.

Bubble sort: the curve that makes O(n²) impossible to ignore

Bubble sort's numbers made the theory impossible to argue with: 100 elements sorted in roughly 0.4 milliseconds, 1,000 elements took about 38 milliseconds — not 10x slower for 10x the data, but closer to 95x slower. By 10,000 elements it took just under 4 seconds, and 20,000 elements took nearly 16 seconds, a four-fold jump for a doubling of input size. That's the "squared" in O(n²) made concrete: doubling the input roughly quadruples the work, because every element still gets compared against nearly every other element, over and over, across repeated passes.

Insertion sort: same complexity class, a genuinely different story on small data

Insertion sort is also O(n²) in the worst case, and the large-array numbers confirmed it — 20,000 elements took about 9 seconds, clearly quadratic-shaped, though noticeably faster than bubble sort at every size tested. What the numbers also showed, and what pure theory doesn't emphasize, is that at 100 elements insertion sort was faster than merge sort: roughly 0.15 milliseconds versus merge sort's 0.3 milliseconds. Big-O describes what happens as input size grows without bound; it says nothing about which algorithm wins on the small, everyday input sizes most real code actually deals with, and that gap between asymptotic behavior and small-input behavior is exactly why some standard library sort implementations quietly switch to insertion sort for small sub-arrays even inside an otherwise O(n log n) algorithm.

Re-running everything on already-sorted input, since that's a common real case

Random data is a reasonable default for a general benchmark, but a meaningful share of real-world sorting happens on data that's already sorted or nearly sorted — re-sorting a list after one new item was appended, for instance — so the same four algorithms were re-timed against fully pre-sorted arrays of the same sizes to see whether the rankings held. Insertion sort's numbers changed dramatically: on pre-sorted data, its worst-case behavior doesn't trigger at all, since each new element is already in its correct position relative to what's been processed so far, and its time on 20,000 pre-sorted elements dropped to under 2 milliseconds — faster than merge sort and quicksort on the same input, a complete reversal of its standing on random data. Bubble sort improved similarly, for the same underlying reason, though it remained the slowest of the four even in its best case. Merge sort's timing barely changed at all between random and sorted input, which makes sense given its divide-and-conquer approach does essentially the same amount of work regardless of the input's existing order — a useful, concrete illustration of the difference between an algorithm's best case and its average case, and a reminder that "which sort is fastest" doesn't have one universal answer independent of what the input actually looks like.

Merge sort: the O(n log n) curve, visible for the first time

Merge sort's numbers were the most satisfying to watch unfold: 1,000 elements in about 0.6 milliseconds, 10,000 elements in about 7 milliseconds, 20,000 elements in about 15 milliseconds. Going from 10,000 to 20,000 elements — doubling the input — roughly doubled the time, not quadrupled it, which is exactly what "n log n" predicts, since log(20,000) is only modestly larger than log(10,000). Watching that ratio hold at each size tested is what finally made "n log n" feel like a real, checkable claim about behavior rather than a phrase to memorize for an interview.

Quicksort: fastest here, and a reminder that "average case" is doing real work in that sentence

Quicksort edged out merge sort at every size in this particular test — 13 milliseconds versus 15 milliseconds at 20,000 elements — which lines up with quicksort's typically lower constant-factor overhead in the average case. The phrase "average case" is worth taking seriously rather than skimming past: quicksort is O(n²) in its worst case, specifically when the chosen pivot repeatedly splits the array as unevenly as possible, which is why a naive quicksort that always picks the first element as pivot performs badly on already-sorted input — a fact that stayed purely theoretical right up until deliberately feeding a pre-sorted array to a first-element-pivot quicksort implementation and watching it degrade to bubble-sort-like timing, confirming the worst case wasn't just a footnote.

What the numbers made concrete that the definitions alone hadn't

• Big-O describes a trend, not a guarantee at any specific size — insertion sort beating merge sort at 100 elements doesn't contradict merge sort's better asymptotic complexity; it confirms that complexity class is about the shape of growth, not a ranking that holds at every input size.
• Constant factors are real and can matter more than complexity class at small scale — two O(n log n) algorithms (merge sort and quicksort) showed a measurable, consistent gap at every size tested, entirely due to differences in per-comparison overhead that Big-O notation deliberately abstracts away.
• "Worst case" isn't a hypothetical footnote — a naive quicksort's worst case is triggered by a specific, realistic input pattern (already-sorted data), not some contrived edge case that never shows up in practice.

Where this actually changed how I write code

The direct, practical payoff wasn't memorizing complexity classes better — it was developing an instinct for when complexity class actually matters for a specific piece of code. A nested loop over a list of 50 items that runs once per page load is not worth restructuring for complexity reasons; the same nested loop over a list that could plausibly grow past a few thousand items, running on every request, is exactly the kind of thing worth catching in review before it becomes the four-minute report. The debugging instinct built while writing a sliding-window rate limiter from scratch came from a similar place: understanding the actual behavior of a data structure under load, not just its name, is what lets you predict where something will break before it does, on a real dataset, in production, rather than after.

A caveat worth stating plainly

None of this is an argument for hand-rolling sort algorithms in real code — every result in this post used custom implementations specifically to observe complexity class differences directly; production code should use a language's built-in, extensively optimized sort (PHP's sort(), in this case) essentially always. The value here was pedagogical: understanding why the built-in sort behaves the way it does, and building the instinct to reach for it (or to recognize when a data structure choice elsewhere in the code, not the sort itself, is the actual bottleneck) — a skill that came directly from timing the difference rather than reading about it, the same way building a small regex engine from scratch exists to build understanding, not to replace a language's real regex engine.