Re:On the Worst-Case Complexity of TimSort
by giovannibajo1 on Friday August 31, 2018 @12:03PM
(#17886642)
It can be done only by adding an initial check that does only that. But this means that the algorithm speed doesn’t gradually increase with partially sorted sequences.
For instance, timsort is also very fast if only a single element is unsorted, or only two elements, or only three elements. These are not special cases explicitly handled, its just the natural way the algorithm works.
For instance, timsort is also very fast if only a single element is unsorted, or only two elements, or only three elements. These are not special cases explicitly handled, its just the natural way the algorithm works.