Insertion sort
Take each element in turn and slide it left past everything larger than it, until it sits in the right place among the elements already handled. How far it has to slide is exactly how many elements to its left are larger than it, so the total work is the number of inverted pairs in the input. On a sorted list there are none, every element stops on its first comparison, and the count is n − 1. On a reversed list every pair is inverted, and the count is n(n−1)/2. The curve plots comparisons, which is what every textbook bound for a sort is about and what makes the four of them directly comparable. The moves are counted too and shown in the panel beside it — worth a look on merge sort, whose comparison count hides the fact that it touches every element on every level.
The claim being tested
O(n) sorted · O(n²) otherwise
When it is the right choice
On small lists, where its tiny constant factor beats an asymptotically better sort outright — most production sorts switch to it below about sixteen elements. And on data that is already nearly in order, where it is genuinely linear rather than merely fast: a list with a handful of elements out of place costs a handful of slides, which no divide-and-conquer sort can match.
How it works
- Treat the first element as a sorted run of one.
- Take the next element and compare it with the element to its left.
- While the element to the left is larger, move it right and keep going.
- Drop the element into the gap. The sorted run is now one longer.
- Repeat to the end of the list.
Worth noticing
- Load the best case against the worst on one pair of axes — the second preset does it — and the two curves leave the same point at n = 8 and end more than three decades apart: 4,095 comparisons against 8,386,560 at n = 4,096. That picture is what "best case" and "worst case" mean, and it is the same twelve lines of code in both.
- The sorted curve is not a quadratic with a small constant. Its gradient is 1, not 2, and no amount of measuring will make it bend upwards, because the inner loop genuinely stops on its first comparison.
- The shuffled curve sits just under half the reversed one, which is the expected number of inversions in a random permutation — n(n−1)/4 — and is a prediction this tool can check rather than assert. It is also the one curve on this page whose bound is an expectation rather than an identity, so it is the one with a visible deviation at the small end.
Cost
- Best
- O(n)
- Average
- O(n²)
- Worst
- O(n²)
- Extra space
- O(1)
- n is
- the length of a list of numbers
- Measures
- shuffled: up to n = 4,096; sorted: up to n = 131,072; reversed: up to n = 4,096
The ceilings are a time limit rather than a memory one, which makes this tool the odd one out in the suite. Its recorded steps are tiny — one step per measured size, not one per operation — so nothing about the trace would ever stop a run. What has to be stopped is the measuring itself: a configuration that would take more than forty million operations to count is refused before a single one of them is counted, from a formula in the input sizes rather than by starting and giving up. Two further limits sit beside it that no formula in operations can see: building the input is real work, and a recursion n deep overflows the call stack long before its operation count becomes interesting.
A fit over a dozen sizes is evidence and not proof. It cannot rule out a term that only begins to matter past the largest size measured, and it says nothing at all about the constant factors that decide which of two algorithms in the same class is actually faster on a real machine.