Menu
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.
843
The algorithm used by sort() is IntroSort. Introsort being a hybrid sorting algorithm uses three sorting algorithm to minimize the running time, Quicksort, Heapsort and Insertion Sort.
Quicksort. Quicksort is one of the most efficient sorting algorithms, and this makes of it one of the most used as well. The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.
When the array is almost sorted, insertion sort can be preferred. When order of input is not known, merge sort is preferred as it has worst case time complexity of nlogn and it is stable as well. When the array is sorted, insertion and bubble sort gives complexity of n but quick sort gives complexity of n^2.
Quicksort. Quicksort is generally thought of as the most efficient 'general' sorting algorithm, where nothing is known about the inputs to the array, and it's more efficient than insertion sort on large lists.
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.
188
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
