Before I start, I want to mention that this algorithm is NOT an 100% viable replacement for table.sort. This was just a passion project of mine that turned out exceptionally well (in some cases, this algorithm outperforms table.sort).
So recently, I’ve been working on a pretty powerful algorithm that I’ve named “AverageSort”. The reason I’ve decided to share this is because I’ve noticed that this algorithm can occasionally outperform table.sort. I’m NOT saying that this algorithm outperforms table.sort entirely, but for a native implementation competing with engine C++ code, it does fairly well.
My algorithm works like how a computer would compress a file. To elaborate, my algorithm takes an array, constructs a shortened dictionary from that array, and uses that dictionary to reconstruct a sorted version of the original array.
In my experiments, I’ve noticed that my algorithm is mostly better than table.sort at sorting large arrays (namely arrays larger than 900). With smaller arrays, my algorithm performs on par or slightly slower than table.sort.
For proof that my algorithm is actually any faster than table.sort, I calculated the time to sort for multiple different table lengths, here are my results:
Benchmark Code
local startClock = os.clock()
sortArray(arrayToSort) -- My sorting algorithm
print("AverageSort Time: "..os.clock() - startClock)
local startClock2 = os.clock()
table.sort(arrayToSort) -- Table.sort
print("QuickSort Time: "..os.clock() - startClock2)
Scores
10 array length
Quicksort Wins
100 array length
Quicksort Wins
1000 array length
Results may vary
10000 array length
AverageSort Wins
100000 array length
AverageSort Wins
1000000 array length
AverageSort definitely wins
According to this data, AverageSort outperforms Quicksort in sorting larger arrays. You may find different results performing these same tests yourself as this heavily relies on CPU power (and I don’t exactly have a good CPU).
Finally, what you’ve all been waiting for, the source. Here it is: GitHub
(Using this algorithm, you agree not to redistribute a closed source version of this under your name).
Feel free to give suggestions or feedback on what you think about this algorithm. I understand that claiming to have created a sorting algorithm faster than the built-in table.sort is a heafty claim, but hopefully it’s justified. If you are still skeptical, feel free to run this algorithm yourself.
(PS; I am unsure if this algorithm already has a name, but I couldn’t find any algorithms that use these same methods that I am.)