Since Timsort is not covered in class, this blog seems like the perfect place to write a few lines about the built-in sorting algorithm in Python. Timsort is a relatively new sorting algorithm, invented by Tim Peters for the Python programming language, and is arguably one of the best sorting algorithms invented so far.
The first thing to note about Timsort is that it is a hybrid sorting algorithm, utilizing both merge sort and insertion sort, and exploiting their respective strengths to achieve a worst case runtime of O(nlogn), which is best a modern sorting algorithm can achieve without the help of customized data structures or hash tables.
One of the central concepts of Timsort is the idea that any random list has a high probability of containing at least one sorted sublist, called 'run', which can be either non-descending or strictly descending. And then there is 'minrun', which is the minimum length of run required by the implementation of Timsort.
First, the algorithm searches for a run, if the run is shorter than the minrun, then items are removed from the remaining list and inserted into the correct position in the list. This process is repeated until all runs are obtained. After that, insertion sort, which is best for short lists, is used to sort the runs. When all of that is done, merge sort is used to merge (and sort) the runs and the remaining list.
Of course, the usage of merge sort and insertion sort in optimal conditions alone will not itself guarantee efficiency of the Timsort algorithm. The part that makes it fast depends on the size of the minrun and the management of the remaining list.
No comments:
Post a Comment