Stable sort for Lua 4.1?

[Reuben Thomas <rrt@...>]

It's rather annoying that sort() is not stable. I have in front of me a copy
of the same book as the Quicksort algorithm you use comes from, and it has
at least one other algorithm which is arguably better than Quicksort, namely
merge sort. This has several advantages:

1. It's simpler (which although it's not of interest to the user, may be to
the Lua developers). For example, it could be implemented non-recursively,
thus improving memory requirements (the current Quicksort is recursive,
though only on the smaller partition).

2. It's guaranteed best case (O(NlogN), although the constant factor may be
higher than for quicksort; however, since the comparator function has high
overhead, I'd've thought the number of comparisons would be critical in
determining the constant factor, rather than the rest of the book-keeping).

3. It's input-insensitive (so its performance is easier to predict than
quicksort's).

4. It's stable. This for me is the big one: I'd like the Lua sort function
to have this desirable property.

You can also find versions of Mergesort which have a linear best-case time,
and are smooth (meaning they degenerate gradually to a worst case of
O(NlogN)).

This would be a really good improvement for 4.1: completely backwards
compatible, adding a useful new ability (to perform stable sorts, which is
required in most database handling applications), and potentially improving
performance all round.

-- 
http://sc3d.org/rrt/ | aphorism, n.  a wise lie