Re: A stable sort

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

2013/5/3 S. Fisher <expandafter@yahoo.com>:
> It's a hybrid merge-insertion sort.  Running under LuaJIT, it's
> pretty fast.

For full compatibility with table.sort, you should insert

    if goes_before(array[1],array[1]) then
      error"invalid order function for sorting"
    end

before calling `merge_sort`.

Here is a comparison under Lua 5.2.2 on a Dell D830 running Linux.
The other three sort programs all make use of precompiled C API functions.
Only one of them is designed to be stable. table.sort is the standard one,
the other two come from the xtable library available from
<http://github.com/dlaurie/xtable>

…/sort$ lua xtable-benchmark.lua 100000
== test on 100000 duples with 20 distinct values
table.sort: 0.50 seconds but is unstable :-(
block.sort: 0.58 seconds and seems stable :-))
xtable.sort: 0.20 seconds but is unstable :-(
Fisher's sort: 0.65 seconds and seems stable :-))
== test on 100000 duples with approximately 20 equals of every value
table.sort: 0.50 seconds but is unstable :-(
block.sort: 0.82 seconds and seems stable :-))
xtable.sort: 0.58 seconds but is unstable :-(
Fisher's sort: 0.54 seconds and seems stable :-))
== test on 100000 random elements
table.sort: 0.16 seconds
block.sort: 0.43 seconds
xtable.sort: 0.24 seconds
Fisher's sort: 0.51 seconds
== test on 100000 sorted elements with 317 random swaps
table.sort: 0.11 seconds
block.sort: 0.34 seconds
xtable.sort: 0.24 seconds
Fisher's sort: 0.40 seconds

This is pretty impressive. You beat block.sort once and run it
close the other times. Despite running in pure Lua.

What's your license?