[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Stablesort 1.2 released
- From: Dirk Laurie <dirk.laurie@...>
- Date: Wed, 15 May 2013 23:07:58 +0200
2013/5/10 Dirk Laurie <firstname.lastname@example.org>:
Version 1.2 of `stablesort` has been released, in the attached
- Call sequence identical to table.sort.
- Relative order of equal elements is never inverted.
- Usually slightly faster, and in some cases much faster,
- 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.
- `benchmark.lua` improved.
- A new file `analysis.txt` discusses some of the underlying
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
Description: Zip archive