[Python-Dev] WikiSort

[Tim Peters]

[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 inplace_stable_sort(), 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 ;-)