IntroSort.lua

local bit_lshift = require("bit").lshift
local math_floor = math.floor
local math_log = math.log

local SIZE_THRESHOLD = 16

local function Partition(Array, Low, High, Value, Comparison)
	if Comparison then
		local Index = Low
		local Jndex = High

		while true do
			while Comparison(Array[Index + 1], Value) do
				Index = Index + 1
			end

			Jndex = Jndex - 1
			while Comparison(Value, Array[Jndex + 1]) do
				Jndex = Jndex - 1
			end

			if Index >= Jndex then
				return Index
			end

			Array[Index + 1], Array[Jndex + 1] = Array[Jndex + 1], Array[Index + 1]
			Index = Index + 1
		end
	else
		local Index = Low
		local Jndex = High

		while true do
			while Array[Index + 1] < Value do
				Index = Index + 1
			end

			Jndex = Jndex - 1
			while Value < Array[Jndex + 1] do
				Jndex = Jndex - 1
			end

			if Index >= Jndex then
				return Index
			end

			Array[Index + 1], Array[Jndex + 1] = Array[Jndex + 1], Array[Index + 1]
			Index = Index + 1
		end
	end
end

local function MedianOf3(Array, Low, Middle, High, Comparison)
	if Comparison then
		local LowPlusOne = Low + 1
		local MiddlePlusOne = Middle + 1
		local HighPlusOne = High + 1

		if Comparison(Array[MiddlePlusOne], Array[LowPlusOne]) then
			if Comparison(Array[HighPlusOne], Array[MiddlePlusOne]) then
				return Array[MiddlePlusOne]
			else
				return Comparison(Array[HighPlusOne], Array[LowPlusOne]) and Array[HighPlusOne] or Array[LowPlusOne]
			end
		elseif Comparison(Array[HighPlusOne], Array[MiddlePlusOne]) then
			return Comparison(Array[HighPlusOne], Array[LowPlusOne]) and Array[LowPlusOne] or Array[HighPlusOne]
		else
			return Array[MiddlePlusOne]
		end
	else
		local LowPlusOne = Low + 1
		local MiddlePlusOne = Middle + 1
		local HighPlusOne = High + 1

		if Array[MiddlePlusOne] < Array[LowPlusOne] then
			if Array[HighPlusOne] < Array[MiddlePlusOne] then
				return Array[MiddlePlusOne]
			else
				return Array[HighPlusOne] < Array[LowPlusOne] and Array[HighPlusOne] or Array[LowPlusOne]
			end
		elseif Array[HighPlusOne] < Array[MiddlePlusOne] then
			return Array[HighPlusOne] < Array[LowPlusOne] and Array[LowPlusOne] or Array[HighPlusOne]
		else
			return Array[MiddlePlusOne]
		end
	end
end

local function HeapSort(Array, Low, High, Comparison)
	if Comparison then
		local Length = High - Low
		local Index = Length / 2
		Index = Index - Index % 1 -- floor

		while Index >= 1 do
			do
				local Value = Array[Low + Index]
				local Child

				while Index <= Length / 2 do
					Child = Index * 2
					if Child < Length and Comparison(Array[Low + Child], Array[Low + Child + 1]) then
						Child = Child + 1
					end

					if Value >= Array[Low + Child] then
						break
					end

					Array[Low + Index] = Array[Low + Child]
					Index = Child
				end

				Array[Low + Index] = Value
			end

			Index = Index - 1
		end

		Index = Length
		while Index > 1 do
			local Value = Low + Index - 1
			Array[Low], Array[Value] = Array[Value], Array[Low]

			do
				local Index2 = 1
				local Length2 = Index - 1
				local Value2 = Array[Low + Index2]
				local Child

				while Index2 <= Length2 / 2 do
					Child = Index2 * 2
					if Child < Length2 and Comparison(Array[Low + Child], Array[Low + Child + 1]) then
						Child = Child + 1
					end

					if Value2 >= Array[Low + Child] then
						break
					end

					Array[Low + Index2] = Array[Low + Child]
					Index2 = Child
				end

				Array[Low + Index2] = Value2
			end

			Index = Index - 1
		end
	else
		local Length = High - Low
		local Index = Length / 2
		Index = Index - Index % 1 -- floor

		while Index >= 1 do
			do
				local Value = Array[Low + Index]
				local Child

				while Index <= Length / 2 do
					Child = Index * 2
					if Child < Length and Array[Low + Child] < Array[Low + Child + 1] then
						Child = Child + 1
					end

					if Value >= Array[Low + Child] then
						break
					end

					Array[Low + Index] = Array[Low + Child]
					Index = Child
				end

				Array[Low + Index] = Value
			end

			Index = Index - 1
		end

		Index = Length
		while Index > 1 do
			local Value = Low + Index - 1
			Array[Low], Array[Value] = Array[Value], Array[Low]

			do
				local Index2 = 1
				local Length2 = Index - 1
				local Value2 = Array[Low + Index2]
				local Child

				while Index2 <= Length2 / 2 do
					Child = Index2 * 2
					if Child < Length2 and Array[Low + Child] < Array[Low + Child + 1] then
						Child = Child + 1
					end

					if Value2 >= Array[Low + Child] then
						break
					end

					Array[Low + Index2] = Array[Low + Child]
					Index2 = Child
				end

				Array[Low + Index2] = Value2
			end

			Index = Index - 1
		end
	end
end

local function IntroSortLoop(Array, Low, High, DepthLimit, Comparison)
	if Comparison then
		::ComparisonStart:: -- this is what makes IntroSort faster than table.sort with jit on AND off.

		while High - Low > SIZE_THRESHOLD do
			if DepthLimit == 0 then
				return HeapSort(Array, Low, High, Comparison)
			end

			DepthLimit = DepthLimit - 1
			local Middle = Low + (High - Low) / 2 + 1
			local Position = Partition(Array, Low, High, MedianOf3(Array, Low, Middle - Middle % 1, High - 1, Comparison))

			Low = Position
			goto ComparisonStart
			-- IntroSortLoop(Array, Position, High, DepthLimit, Comparison)
			High = Position
		end

		do
			local Index = Low
			local Jndex, Value

			while Index < High do
				Jndex = Index
				Value = Array[Index + 1]
				while Jndex ~= Low and Comparison(Value, Array[Jndex]) do
					Array[Jndex + 1] = Array[Jndex]
					Jndex = Jndex - 1
				end

				Array[Jndex + 1] = Value
				Index = Index + 1
			end
		end
	else
		::NoComparisonStart::
		while High - Low > SIZE_THRESHOLD do
			if DepthLimit == 0 then
				return HeapSort(Array, Low, High)
			end

			DepthLimit = DepthLimit - 1
			local Middle = Low + (High - Low) / 2 + 1
			local Position = Partition(Array, Low, High, MedianOf3(Array, Low, Middle - Middle % 1, High - 1))
			Low = Position
			goto NoComparisonStart
			-- IntroSortLoop(Array, Position, High, DepthLimit)
			High = Position
		end

		do
			local Index = Low
			local Jndex, Value

			while Index < High do
				Jndex = Index
				Value = Array[Index + 1]
				while Jndex ~= Low and Value < Array[Jndex] do
					Array[Jndex + 1] = Array[Jndex]
					Jndex = Jndex - 1
				end

				Array[Jndex + 1] = Value
				Index = Index + 1
			end
		end
	end
end

local function IntroSort(Array, Comparison)
	local Length = #Array
	IntroSortLoop(Array, 0, Length, bit_lshift(math_floor(math_log(Length, 2)), 0), Comparison)
end

return IntroSort

this is much faster than table.sort on luajit by the way