local swap =
function (self, x, y)
self[x], self[y] = self[y], self[x]
end
local greater_comp =
function (x, y)
return x > y
end
-- {{{ quicksort
-- forward-declare
local qsort = nil
qsort =
function (seq, first, last, gt, depth)
if depth == 0 then error('shiiiiiit nigga') end
if first < last then
local i, p, j = first, first, last
while i < j do
local pivot = seq[p]
while not gt(seq[i], pivot) do i = i + 1 end
while gt(seq[j], pivot) do j = j - 1 end
if i < j then
swap(seq, i, j)
end
end
swap(seq, p, j)
depth = depth - 1
qsort(seq, first, j - 1, gt, depth)
qsort(seq, j + 1, last , gt, depth)
end
end
local quicksort =
function (seq, gt, i, j, depth)
i, j = 1, #seq
gt = gt or greater_comp
depth = depth or math.huge
print('>', 'quicksort')
qsort(seq, i, j, gt, depth)
end
-- }}}
-- {{{ heapsort
local left = function (i) return i * 2 end
local right = function (i) return i * 2 + 1 end
local parent = function (i) return math.floor(i / 2) end
local build =
function (seq, gt, i, j)
end
-- }}}
-- {{{ introsort
local introsort =
function (seq, gt, i, j)
print('>', 'introsort')
if not pcall(quicksort, seq, gt, i, j, math.log(#seq, 2) * 2) then
heapsort(seq, gt, i, j)
end
end
-- }}}
-- {{{ insertionsort
local insertionsort =
function (seq, gt, i, j)
i = i or 1
j = j or #seq
gt = gt or greater_comp
print('>', 'insertionsort')
for x = i, j do
local tmp, y = seq[x], x
while y > i and gt(seq[y - 1], tmp) do
seq[y] = seq[y - 1] -- slide up
y = y - 1
end
seq[y] = tmp
end
end
-- }}}
local tiny_limit = 16
local polysort =
function (seq, gt, i, j)
if (i and j and j - i - 1 <= tiny_limit) or #seq <= tiny_limit then
insertionsort(seq, gt, i, j)
return
end
introsort(seq, gt, i, j)
end