stack based merge sort

mergesort.luau

--!strict
local function decodePair(pair: number): (number, number)
	-- Get the vertex A and B
	return bit32.rshift(pair, 16), bit32.band(pair, 0xFFFF)
end

local function encodePair(a: number, b: number): number
	-- Encode A and B
	return bit32.bor(bit32.lshift(a, 16), b)
end

local function mergeRun<T>(
	arr: { T }, temp: { T },
	leftCursor: number, rightCursor: number,
	bound: number, comp: (T, T) -> boolean
)
	if leftCursor == rightCursor then
		-- Don't need to do anything fancy here.
		return
	elseif leftCursor + 1 == rightCursor then
		-- We only need to do one swap if necessary
		if not comp(arr[leftCursor], arr[rightCursor]) then
			arr[leftCursor], arr[rightCursor] = arr[rightCursor], arr[leftCursor]
		end
		
		return
	end
	
	local midpoint = rightCursor - 1
	local left = leftCursor
	for i = left, bound do
		if leftCursor > midpoint then
			-- Choose the right
			temp[i] = arr[rightCursor]
			rightCursor += 1
		elseif bound < rightCursor then
			-- Choose the left
			temp[i] = arr[leftCursor]
			leftCursor += 1
		elseif comp(arr[leftCursor], arr[rightCursor]) then
			-- Right side greater
			temp[i] = arr[leftCursor]
			leftCursor += 1
		else
			-- Left side greater
			temp[i] = arr[rightCursor]
			rightCursor += 1
		end
	end
	
	for i = left, bound do
		-- Do this!
		arr[i] = temp[i]
	end
end

return function<T>(arr: { T }, left: number, right: number, comp: (T, T) -> boolean)
	local temp = table.create(right - left + 1)
	local bits = 32 - bit32.countlz(right - left + 1)
	
	for bit = 1, bits do
		local half = bit32.lshift(1, bit - 1)
		local exp = bit32.lshift(1, bit)

		for i = left, right, exp do
			-- Merge between the left and right
			-- subarrays.
			mergeRun(
				arr, temp,
				i, math.min(i + half, right),
				math.min(i + exp - 1, right), comp
			)
		end
	end
end