[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: A stable sort**
**From**: Dirk Laurie <dirk.laurie@...>
**Date**: Fri, 3 May 2013 07:51:49 +0200

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?