Adaptive Algorithms
Timsort on already sorted input finds a single run and finishes in one pass.
More 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.
Cost
- Space
- O(1)
Before this
Related
Taught by the same lesson
More Sorts covers these too, in the same run.