> In the worst case, Timsort takes O(n logn) comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm.
Python has a sorting HOWTO at https://docs.python.org/3/howto/sorting.html . I was the original author, back in around 1998 or so. This new article covers a subset of that HOWTO.
3 comments
[ 3.9 ms ] story [ 26.3 ms ] thread> In the worst case, Timsort takes O(n logn) comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm.