I'm curious what algorithm Lua's default table.sort uses, only because it's slower than some other sorting algorithms I've come across. I'm also curious if Lua's table.sort is written in the Engine in C, or if it's in a library in Lua.
5
votes
2 Answers
6
votes
What algorithm does table.sort use?
The comment in tablib.c (scroll up a bit) states
/*
** {======================================================
** Quicksort
** (based on `Algorithms in MODULA-3', Robert Sedgewick;
** Addison-Wesley, 1993.)
** =======================================================
*/
You can read the source code at the link I provided.
I'm also curious if Lua's table.sort is written in the Engine in C, or if it's in a library in Lua.
At this time, all libraries that come directly with Lua (io, table, math, ...) are written in C.
3
votes
Internally, table.sort uses quicksort, and it's written in C. Note that quicksort is not stable. And a little bit surprisingly to me, Lua didn't use C's qsort() directly.
As to performance, it's hard to tell since there are various factors, for example, what language and what algorithm you are comparing with, and what kind of data is being tested.