Re: A stable sort

["S. Fisher" <expandafter@...>]

I don't know much about licenses.  Let's say the code is in
the public domain.

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.

Steve Fisher

--- On Fri, 5/3/13, Dirk Laurie <dirk.laurie@gmail.com> wrote:

> From: Dirk Laurie <dirk.laurie@gmail.com>
> Subject: Re: A stable sort
> To: "Lua mailing list" <lua-l@lists.lua.org>
> Date: Friday, May 3, 2013, 12:51 AM
> 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?
> 
>