Python's sort is nearly free on data that is almost sorted
Sorting a million random floats with list.sort() took 111 ms in Python 3.14. Sorting the same list after it was already in order took 7 ms, and a sorted list with a thousand elements swapped at random took 16 ms. Sort time tracks how many "runs" the data contains, not how big it is, and a few out-of-place items barely register.
The test
One million random floats, copied before each sort, median of 7 runs, in a container with 2 CPUs. Times in milliseconds.
| input | ms | vs random |
|---|---|---|
| random | 111 | 1x |
| already sorted | 7.2 | 15x faster |
| reversed | 9.0 | 12x faster |
| sorted + 0.01% random swaps | 6.8 | 16x |
| sorted + 0.1% random swaps | 8.4 | 13x |
| sorted + 1% random swaps | 15.7 | 7x |
| sorted + 10% random swaps | 50 | 2.2x |
| sorted + 1% random items appended | 7.7 | 14x |
| sorted + 10% random items appended | 17 | 6.4x |
| 2 sorted runs back to back | 15 | 7x |
| 10 sorted runs | 32 | 3.5x |
| 100 sorted runs | 49 | 2.3x |
| 1,000 sorted runs | 65 | 1.7x |
| 10,000 sorted runs | 75 | 1.5x |
Why
Python's sort (Timsort) first scans for runs that are already ascending, or strictly descending, which it reverses in place. A fully sorted list is one run: one pass of a million comparisons, about 7 ns each, and nothing else. Data made of a few long runs is merged, and the merge "gallops": when one side keeps winning it jumps ahead by doubling steps instead of comparing one at a time, so merging two big runs that barely interleave costs little. That is why 1% appended random items (which end up as a short tail to sort and then slot in) cost almost nothing extra, and why a few swaps hardly matter. Cost rises toward the random case as the number of runs grows, but even 10,000 runs of 100 items stayed 1.5x faster than random.
So what
Re-sorting a list after a handful of changes, or after appending new items to an already sorted one, is cheap, so there is usually no reason to maintain a special "insert in order" structure just to avoid the sort. Calling sort() on a nearly sorted log, leaderboard or time series is close to a single pass. It doesn't rescue you from heavy disorder: at 10% of items swapped, the gain was only 2x.
Method: one machine, a 25-line script, Python 3.14 in a container. Floats only; I didn't measure strings, tuples or key functions.