Native Implementation sorting algorithm occasionally faster than table.sort

AverageLua · April 2, 2021, 7:30pm

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

colbert2677 · April 2, 2021, 8:36pm

I guess more specifically you could say that this algorithm is only useful for sorting arrays where the values are numerical. Any other use case for table.sort, especially those that require the sorting function parameter, fall through.

There are a few variables missing from the code and I’m not sure what to fill them with. When posting the raw of the code file into Studio, several items have blue outlines. Could you check those out and update the code file with the relevant missing pieces?

For getLargestNumber, you could hypothetically just use a single line to determine this rather than a function which performs iteration across all of the array’s elements. Is that something you’ve tried before and found not to work? I’d like to test myself but with the aforementioned missing elements and no guidance on what to put in their place, I’m lost there.

-- Get the largest number after unpacking the elements of an array
math.max(table.unpack(array))

(Yes, I’m aware the comparison would fail if there’s another datatype in the array. That’s not the point I’m making so I’m not looking for that to be pointed out. Just in case anyone asks.)

AverageLua · April 2, 2021, 9:07pm

Yes, I forgot to mention that, my algorithm only supports numerical values as sorting out how it would work with string values would be a nightmare. Sorry about the source as well, I updated the GitHub with the correct elements now.

Btw thanks for pointing that out with getting the largest number.
Edit: After actually trying your suggested fix, it gives an error saying “too many results to unpack”. It seems for now I’ll have to stick to using the for loop.

colbert2677 · April 2, 2021, 9:19pm

Thanks for letting me know though. Since I did pitch the suggestion but was unable to test it, I wasn’t completely sure if what I said would work in this case. I guess the math.max trick only works for smaller tables which is what I’m used to handling.

AverageLua · April 2, 2021, 9:26pm

Your solution actually still kind of works now that I’ve played with it a bit. In the “getLargestNumber” I can check if the size of the array is less than 8000 (the max amount that can be unpacked) and then act accordingly. I’ve implemented this and updated the GitHub.

goldenstein64 · April 10, 2021, 7:49am

I have a feeling you can sort anything with this algorithm as long as you can turn whatever value it is into a “sizable” integer.

e.g. you can turn strings into sizable integers by adding up the byte values and multiplying them by something according to their position in the string:

-- the range of [0, SEP] + OFFSET
local SEP = 255
local OFFSET = 0

local function hash(str)
	local bytes = table.pack(string.byte(str, 1, -1))
	local result = 0
	for i, byte in ipairs(bytes) do
		result += (byte - OFFSET) * SEP^(bytes.n - i)
	end
	return result
end

local function dehash(num)
	local result = {}
	local start = math.floor(math.log(num, SEP))
	for i = start, 0, -1 do
		local letter = string.char(math.floor(
			(num / (SEP^i)) % SEP + OFFSET
		))
		table.insert(result, letter)
	end

	return table.concat(result)
end

This only works for some strings at 7 characters and all the strings lower than 7, because integers can only hold up to 53 bits of precision (so up to 9.00719925e+15), and each letter in the integer would take 8 bits.

local function test(str)
	local num = hash(str)
	print(num, dehash(num))
end

test("someth") --> 1.2446459936458e+14 someth
test("somethi") --> 3.1738472837969e+16 somethh -- notice the corruption

If we were to only include the 26 lowercase letters (or SEP = 25; OFFSET = 97), then we could increase its storage to 11 characters.

storage calculation

local function getSize(sep)
    return 53 / math.log(sep + 1, 2)
end

It might be more useful if you can find the minimum of all the values and start your for loop there (you can include it in the loop of your getGreatestNumber function).

Algorithm analysis:

place all values in the hash table as value-count pairs, O(n)
find the greatest (and possibly least) number in the array, O(n)
loop from the least to the greatest using a numerical for loop.
- this last step is entirely value-dependent, so its Big O would depend on the range of values the array has. If we say p, q is the min, max, then it would be around O(n + q - p)

I’m sure you’ve been testing with arrays that are generated like this:

local R = Random.new()

local array = {}
for i = 1, RANGE do
    array[i] = R:NextInteger(1, RANGE)
end

You should test for edge cases like:

having a small range with a large number of values, which should be more efficient and very close to O(n) (better than the best general sorting algorithms, O(n log n))
having a large range (like up to 9e15) with a small number of values, which would probably lead to somewhere around O(n + 9e15)

I finally found an algorithm very similar to yours, known as counting sort:

It has the same advantages and drawbacks of your own sorting algorithm, but the pseudocode is different from yours, so I guess you can compare the two and see where they differ!

weeeeeeeeeel · April 10, 2021, 9:20am

Conting sort is O(n + k), k being the range in the array. This becomes very ineffective for arrays with large ranges
Example;

local table = {1, 10,000}