On 09/11/2016 10:48 PM, Terry Reedy wrote: [...] > Second, with respect to timsort in particular: timsort is designed to > exploit structure and run faster than O(n*logn) in special cases. If a > list is already sorted, timsort will do one O(n) scan and stop. Any > radix sort will take several times longer. If a list is reverse sorted, > timsort will do one O(n) scan and do an O(n) reverse. If a list is the > concatenation of two sorted lists, timsort will find the two sorted > sublists and merge them. If a sorted list has unsorted items appended > to the end, timsort will sort the appended items and then do a merge. I > expect any radix sort to be slower for all these cases. Tim Peters > somewhere documented his experiments and results with various special > but plausible cases of non-randomness. That write-up is included in Python source: https://github.com/python/cpython/blob/master/Objects/listsort.txt A good read if you want to know what sort of thinking, benchmarking, and justification should go into a new sorting algorithm.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4