Adaptive Algorithms
Timsort on already sorted input finds a single run and finishes in one pass.
Decision · step 2 of 4More Sorts: Timsort on sorted input
From index 0 the values keep rising for 8 slots: a natural run of length 8. That is at least 4, so it is taken as it is.
What you will see
Insertion sort on nearly sorted input finishes in a fraction of the steps.
Cost
| Space | O(1) |
|---|
How you work with it here
explore, compare two runs, run it on your own input.
Screen readers: Growth curves are described in words and as a table of operation counts for sample input sizes; each concept has a one-sentence spoken definition.
Reduced motion: Curves and counters update without animation.
Before this
Related
Taught by the same lesson
More Sorts covers these too, in the same run.