AlgoScope

TimSort

Find natural ascending runs, extend short ones by insertion sort, then merge neighbouring runs.

Sorting, algorithm, advanced
Natural run of 5 from index 0.run 0-4308112220325425961476819
Natural run of 5 from index 0.run 0-4308112220325425961476819

More Sorts: Timsort finds two natural runs

Decision, step 2 of 33

From index 0 the values keep rising for 5 slots: a natural run of length 5. That is at least 4, so it is taken as it is.

How more sorts works

Cost

Best
O(n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)

Properties

  • Yes: Comparison based
  • Yes: Stable
  • No: In place
  • Yes: Adaptive
  • No: Online

Taught by the same lesson

More Sorts covers these too, in the same run.