lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

I supposed it to be quicksort, just didnt bother to RTFSC.

> 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)

[1] I doubt it anybody soon, but maybe I'm just ignorant after almost
20 years nothing happening in this field anymore. Likely quantum
computing might change the game, but if it will change everything in
informatics anyway. Nevertheless it wouldn't change behavior middle in
a revision and Lua never had a problem of breaking the API between

I'd consider O() behavior not an unimportant "implementation detail",
but a significant part of the interface that is doc-worthy. E.g. for
some it maybe worth it to replace it with insertion sort, since in
many cases you can fairly assume already sorted data, but have to make
sure because your API doesn't demand it.