[Python-Dev] WikiSort (original) (raw)

Tim Peters tim.peters at gmail.com
Sat Mar 15 22:51:48 CET 2014

[Aahz <aahz at pythoncraft.com>]

[I'm nomail -- Cc me if you care whether I see followups]

https://github.com/BonzaiThePenguin/WikiSort/tree/master WikiSort is a stable bottom-up in-place merge sort based on the work described in "Ratio based stable in-place merging", by Pok-Son Kim and Arne Kutzner [PDF]. Kim's and Kutzner's algorithm is a stable merge algorithm with great performance characteristics and proven correctness, but no attempt at adapting their work to a stable merge sort apparently existed. This is one such attempt! Probably no interest in switching over, but there might be a trick or two to add to TimSort.

It's the "in-place" here that's novel - a stable merge sort that doesn't require extra memory. C++ library authors may wish to look at this for that reason; the WikiSort text says:

* 3-15x faster than inplacestablesort(), which is libc++'s equivalent O(1) sort function.

Last I looked, the C++ template library's inplace_stable_sort() used a merge sort variation that bought constant memory use at the cost of making runtime O(N * log(N)**2) (although the asymptotics weren't documented, they were easy enough to deduce). That's why "3-15x" isn't surprising. A similar trick could be grafted into the guts of Python's sort to ensure constant memory use, but with a similar slowdown.

But the tricks in WikiSort can't be grafted into Python's sort. It's a fundamentally different approach. I expect Python's sort still does significantly fewer comparisons, which is the most important thing to count for Python's sort (moving pointers around is "almost free" compared even to comparing integer objects in CPython).

A very cool thing about the Kim & Kutzner paper is that the method there gracefully handles merging two vectors with very different sizes. For an extreme example, consider merging a vector of size 1 with a vector of size 1000000. "The standard" merge algorithm may require a million comparisons to do that, but it's obvious it can be done with only about 20 comparisons by using a binary search to find where the single element in the first vector belongs K&K adapt to that.

So does Python's sort, but with a higher (although still logarithmic) upper bound on the number of comparisons needed.

But WikiSort is a "bottom-up" mergesort, and is set up to guarantee that, at any point, the two areas it's currently merging never differ in size by more than 1 element. So the potential for exploiting K&K's nice adaption to wildly different sizes can't be tapped. It does have other adaptive properties, although I bet Pyhon's current sort can exploit a lot more kinds of partial regularity.

Finally, if you thought Python's sort was hard to understand ... you're partially right ;-) But it's really just a large number of tricks each of which is easy enough to understand on its own. Efficient in-place merge algorithms are inherently tricky. Indeed, one remarkable aspect of the K&K paper is that the authors actually implemented their algorithm; most prior attempts were so complex that the authors stopped after proving correctness - actually writing code to implement the mess was too depressing ;-)

More information about the Python-Dev mailing list