Re: A stable sort

[Dirk Laurie <dirk.laurie@...>]

2013/5/8 S. Fisher <expandafter@yahoo.com>:
> I don't know much about licenses.  Let's say the code is in
> the public domain.

The problem with "public domain" is that anybody can claim to
have written it himself, distribute it without mentioning the fact
that it is in the public domain, and fool people into paying him
royalties. All he can't successfully do is sue them if they don't.

However, it also allows me to what I have described below,
so there is no harm done.

> I believe that the default sort routine in all languages
> should be stable.  The instability of the sort in Ruby
> (at least in version 1.8.7) has caused me grief.
>
> If stable-sorts can be made as fast as unstable-sorts then
> it is to be hoped that all languages will use stable sorts.
> That can only make things easier for the users.

I have partially re-implemented Steve's routine so that the two critical
routines for sorting small arrays directly and for merging two adjacent
sorted arrays are coded in in C. Since the intention is that the routine
will be used with Lua, I have made the license the same as Lua's, which
stops the sort of tomfoolery that public domain allows. With Steve's
permission, I've listed both of us as authors.

The use of core C routines shaves 20%-25% off the time of the pure Lua
version when a user-supplied compare is used, and more than 60% for
the default less-than compare, since the C routines can do that without
calling Lua. It also easily beats the stable xtable.block.sort that
I was using up to now.

In fact, the performance is comparable with table.sort. ("Cut deck"
means the second half of a sorted array followed by the first.)

…/sort$ lua sort-benchmark.lua 1000000
== test on 1000000 duples with 20 distinct values
table.sort: 6.62 seconds but is unstable :-(
stablesort: 6.64 seconds and seems stable :-))
== test on 1000000 duples with approximately 20 equals of every value
table.sort: 6.82 seconds but is unstable :-(
stablesort: 4.80 seconds and seems stable :-))
== test on 1000000 random duples
table.sort: 7.43 seconds
stablesort: 6.99 seconds
== test on 1000000 cut deck
table.sort: 2.66 seconds
stablesort: 1.39 seconds
== test on 1000000 sorted elements with 1000 random swaps
table.sort: 1.46 seconds
stablesort: 1.78 seconds

I append a zipfile.

This version does not work with LuaJIT, but presumably the pure Lua
version would already be hard to beat.

Attachment: stablesort-1.0.zip
Description: Zip archive