Re: Is there any reason not to have sort function from C API?

[Dirk Laurie <dpl@...>]

On Wed, Aug 17, 2011 at 12:01:35PM +0200, Axel Kittenberger wrote:
> 
> BTW: Why does the manual not describe which algorithm is used and how
> it performs on sorted, unsorted, and reverse-sorted data?
> 

1. That's an implementation detail.
2. If you really want to know, look in Lua's source code.  It is open.  
   In ltable.c, look for 'sort' and find 
** Quicksort
** (based on `Algorithms in MODULA-3', Robert Sedgewick;
**  Addison-Wesley, 1993.)
3. If that answer does not tell you what you need to know, read
    the Wikipedia article on Quicksort.

Maybe tomorrow some pair of computer science students turns in a 
project, which their professor then publishes as a joint effort, [1]
in which a sorting algorithm with all these properties is presented:

  1. O(n*log(n)) worst case time
  2. O(n) on sorted and reverse-sorted data
  3. O(1) auxiliary storage
  4. Stable (items with equal keys remain in the same order
      as at the start)

At that stage one would not want Lua's sort algorithm to be
cast in stone in the manual as having only property (2).

Dirk

[1] As actually happened for another long-standing problem.
 <http://en.wikipedia.org/wiki/AKS_primality_test>