TimSort came into existence in year 2002 and Python has been using TimSort for in built sort function from version Python 2.3. But What about the earlier versions?
Asked
Active
Viewed 191 times
0
-
in continuation with https://stackoverflow.com/questions/1517347/about-pythons-built-in-sort-method? – Trying to be a programmer Jun 11 '20 at 00:15
1 Answers
2
Based on this Python bug tracker entry, it looks like the previous implementation was a samplesort.
It was originally proposed as a second means of sorting, but by the time it was accepted and merged, they decided to replace samplesort completely.
ShadowRanger
- 143,180
- 12
- 188
- 271
-
Elsewhere, Tim Peters calls it the original algorithm a "[highly tuned samplesort hybrid](https://bugs.python.org/file4451/timsort.txt)." – Brian McCutchon Jun 11 '20 at 00:28
-
-
@RaghavPuri: The Wikipedia article provides that information on samplesort. In practice, the reasons for choosing TimSort are provided in that Python bug tracker entry; it's stable, and it runs *much* faster when the input data is already partially sorted (making it ideal for Python, with one sort to rule them all, so doing `sortedlist1 += sortedlist2`, then `sortedlist1.sort()`, isn't doing full `O(n log n)` work to reestablish the sort invariant, largely removing the need for optimized "merge sorted sequences better than re-sorting" code). It also does slightly fewer comparisons. – ShadowRanger Jun 12 '20 at 13:55