This module provides an alternative to table.sort that is stable, i.e. guarantees that elements considered equal by the given order will keep their relative positions.
It supports the same parameters as table.sort; the first parameter is the array to sort, and the second (optional) parameter is a comparison function, which returns true if and only if the first parameter is less than the second. If the comparison function is not specified, the default less-than operator < is used.
This function ranges anywhere from slightly to significantly slower than table.sort and should only be used in cases where sorting stability is a requirement.
local function table_len(...)
table_len = require("Module:table").length
return table_len(...)
end
-- insertion sort: sort part of array tbl ... tbl with comparison function less
local function sort_insertion(tbl, less, i0, i1)
local i = i0 + 1, j
while i <= i1 do
j = i
-- this is faster, but unfortunately not well defined if less causes an error.
-- local tmp = tbl
-- while j > i0 and ((less and less(tmp, tbl)) or (not less and tmp < tbl)) do
-- tbl = tbl
-- j = j - 1
-- end
while j > i0 and ((less and less(tbl, tbl)) or (not less and tbl < tbl)) do
tbl, tbl = tbl, tbl
j = j - 1
end
i = i + 1
end
end
-- merge: merge runs src ... src and src ... src with comparison function less
-- and output merged run into dst ... dst
-- note: assumes i0 < i2 and i2 <= i3 for performance reasons.
local function sort_merge(dst, src, less, i0, i2, i3)
local i1 = i2 - 1
-- left and right run pointers
local a, b = i0, i2
local i, j
for j = i0, i3 do
if (less and less(src, src)) or (not less and src < src) then
-- src > src: item from right run
dst = src
if b >= i3 then
-- remaining items from the left run
for i = a, i1 do
j = j + 1
dst = src
end
return
end
b = b + 1
else
-- src <= src: item from left run
dst = src
if a >= i1 then
-- remaining items from the right run
for i = b, i3 do
j = j + 1
dst = src
end
return
end
a = a + 1
end
end
end
local function stable_sort(tbl, comp)
local b, n = 1, table_len(tbl) -- start and end of table
local i, k -- index, merge increment
local k = 8
local sort_insertion = sort_insertion
for i = b, n, k do
-- insertion sort for small blocks
local e = i + k - 1
if e > n then e = n end
sort_insertion(tbl, comp, i, e)
end
-- no need to merge, array is small enough
if n <= k then return end
-- merge sort the rest from the bottom up; now we have
-- runs of K all sorted
local buf = {}
-- to avoid copies, swap between two buffers on every iteration
local src, dst = tbl, buf
local sort_merge = sort_merge
repeat
local k2 = k + k
for i = b, n, k2 do
-- e.g. k = 8: we take two 8-item blocks and merge into a 16-item one
-- start of right run
local s = i + k
if s > n then
-- copy remaining from src to dst
for j = i, n do
dst = src
end
break
end
-- end of right run
local e = s + k - 1
if e > n then e = n end
sort_merge(dst, src, comp, i, s, e)
end
k = k2 -- double k
-- swap buffers
src, dst = dst, src
until k >= n
if src ~= tbl then
-- final sorted array in buf; copy back to tbl
for i = b, n do
tbl = src
end
end
end
return stable_sort