There are cases where pattern defeating sort beats timsort
https://github.com/EmuraDaisuke/SortingAlgorithm.HayateShiki
Timsort, the Python sorting algorithm
11–20 of 135 posts
Re: Timsort, the Python sorting algorithm
#12Earlier quoted context omitted.
Not true in general, however IIRC it is the case if you want optimal (i.e. n log n) time complexity.
Not even in that case. Heapsort guarantees worst case n log n, and so does quicksort if you use an O(n) median selecting algorithm. Stable sorts often do require that, (mergesort is usually stabble, heapsort and quicksort are inherently not), but even that's not required - there is a completely in-place variant of merge sort that only requires O(log n) space for stack (like quicksort; heapsort is O(1)). See e.g. http…
Apparently there is a O(n log n) time, O(1) space, stable sort: https://en.wikipedia.org/wiki/Block_sort
Re: Timsort, the Python sorting algorithm
#13Rust uses timsort as the stable sorting algorithm in its standard library.
https://doc.rust-lang.org/std/primitive.slice.html#method.so...
Re: Timsort, the Python sorting algorithm
#14WikiSort should even be faster still
Original author: https://github.com/BonzaiThePenguin/WikiSort
Graph and copyage (by me): https://tse.gratis/aArray/#details
Or grail sort: https://github.com/Mrrl/GrailSort/blob/master/README.md
Sort, is a deep rabbit hole
Re: Timsort, the Python sorting algorithm
#15Heard about it by reading Java stacktraces one day.
Re: Timsort, the Python sorting algorithm
#16Tim Peters is also the IEEE-754 guru for the Python codebase.
Truly a giant of the Python community.
Re: Timsort, the Python sorting algorithm
#17WikiSort should even be faster still Original author: https://github.com/BonzaiThePenguin/WikiSort Graph and copyage (by me): https://tse.gratis/aArray/#details Or grail sort: https://github.com/Mrrl/GrailSort/blob/master/README.md Sort, is a deep rabbit hole
WikiSort previous discussion
https://news.ycombinator.com/item?id=7404223
Can't find a direct comparison with TimSort though..
Re: Timsort, the Python sorting algorithm
#18My favourite TimSort story is of ex-Sun employee, Joshua Bloch of Effective Java fame. J Bloch was in audience at the time when Tim Peters presented his new algorithm to sort a list, and he was so blown away that he started porting Tim's implementation right there with an intent to commit it to the JDK mainline [0], which he eventually did [1].
[0] Some of the core JDK developers are really on another level. The JDK code, post 1.5, is a joy to read, though verbose. Compilers and Languages seems to attract a certain caliber of engineers, I think.
Re: Timsort, the Python sorting algorithm
#19Tim the enchanter!
Re: Timsort, the Python sorting algorithm
#20Earlier quoted context omitted.
Note that this is true for any (edit: stable, nlogn) merge sort.
you can do merge sort in place
You can’t. Merge sort copies data back and forth between two spaces the size of the data set. That’s O(n) extra space.
I spent some time four summers ago with merge sort. I had a PoC for an in-place algorithm that survived several rounds of poorly selected sample data. That was quite a disappointment.
In looking around I believe I ran across several implementations that required sqrt(n) extra space and one that I think claimed log n but was so complicated I never did figure out why it was supposed to work. At least one of these had higher time complexity, but often enough you need to work with data sets that dominate your memory footprint. Even a second array of pointers might push you over.