Hello there,
I've been wanting to sort numbers in a table using the most efficient method possible. I looked up what the most efficient method was, basically in Big O notation, that would be O(n * log(n)). Which decreases the workload on the server and takes into account scalability.
I looked up how the MergeSort works and they talked about Recursion and such. Apparently, you divide the table in half, and compare the two halves' values with each other to sort them. However, you keep on doing that using recursion until the table can't be divided into two anymore. Except, I don't understand how this would work for an uneven amount of values and how does the whole system work step-by-step?
##Any help is appreciated, thank you.
3 comments
First off, I don't know what sorting method table.sort() uses, and also, I wanted to understand merge sort because it is the most efficient sorting method. In Big O Notation, it's O(n * log(n)) which means that on a bigger scale, the workload is little. So, I was thinking about scalability. I want efficient code that works no matter what the scale of the problem is. So, scalability matters.
Lua's table.sort() method uses the quick sort algorithm. This algorithm at it's best can be O(n * log(n)) but in the worst case scenario it could be O(n^2), however the average case is much more often the best case than the worst. However, I still highly recommend using the built in table.sort(). To be continued:
Lua is an interpretation language. Even if you write your own quick sort algorithm that works exactly the same as table.sort(), you will find that it takes a longer time to sort the same table than table.sort() does, because the latter is already written in C and therefore does not have to be interpreted as a bunch of Lua code before usage. I really hope this helps!