Stablesort 1.2 released

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

2013/5/10 Dirk Laurie <dirk.laurie@gmail.com>:

Version 1.2 of `stablesort` has been released, in the attached
zipfile.

Features:

  - Call sequence identical to table.sort.
  - Relative order of equal elements is never inverted.
  - Usually slightly faster, and in some cases much faster,
    than table.sort.
  - Control routine is in Lua, subroutines in C. A modification
    allowing optional range parameters as does table.concat
    would be trivial.

Algorithmic improvements over 1.1:

  - Testing for sorted subchunks is now the default.
  - Insert sort for small chunks keeps the whole chunk on the stack.

Documentation improvements:

  - `benchmark.lua` improved.
  - A new file `analysis.txt` discusses some of the underlying
    issues.

Here is the contents of the file `benchmark.out`.


== test1: 1000000 random duples
== test2: 1000000 cut deck
== test3: 1000000 sorted elements with 1000 random swaps
== test4: 1000000 duples with 20 distinct values
== test5: 1000000 duples with approximately 20 equals of every value
== test6: permutation of 1:32768 designed as a worst case for quicksort

     Time in seconds, negative time means sort was unstable

                    #1     #2     #3     #4     #5     #6    Total
      table.sort   7.05   2.76   1.54  -7.09  -7.28  20.19   45.91
      stablesort   7.05   0.38   1.43   7.00   5.15   0.03   21.04

Attachment: stablesort-1.2.zip
Description: Zip archive