AlgoScope

Adaptive Algorithms

Timsort on already sorted input finds a single run and finishes in one pass.

Complexity analysis, analysis, intermediate
Natural run of 8 from index 0.run 0-710416293134205216307
Natural run of 8 from index 0.run 0-710416293134205216307

More Sorts: Timsort on sorted input

Decision, step 2 of 4

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.

How more sorts works

Cost

Space
O(1)

Taught by the same lesson

More Sorts covers these too, in the same run.