  lua-l archive

• Subject: Re: A stable sort
• From: Eike Decker <zet23t@...>
• Date: Wed, 8 May 2013 13:31:09 +0200

2013/5/8 Eike Decker

2013/5/3 S. Fisher

It's a hybrid merge-insertion sort.  Running under LuaJIT, it's
pretty fast.

I only wrote this quickly and haven't given it intensive testing, but this sort function is pretty simple, short, stable and fast (only tested your function in vanilla Lua - it performed about 20% faster) - so without warranty, here's the code:

Typo, one line when MIA somehow:

--- sorts arr in a stable manner via a simplified mergesort
-- the simplification is to avoid the dividing step and just start
-- merging arrays of size=1 (which are sorted by definition)
function msort_inplace(arr, goes_before)
local n = #arr
local min = math.min
local step = 1
local fn = goes_before or function(a,b) return a < b end
while step < n do
for i=1,n,step*2 do
local s1,s2 = i, i + step
local e1,e2 = min(s2-1,n), min(s2+step,n)
local a,b = s1,s2
local pos = a
while a <= e1 and b <= e2 do
local va,vb = arr[a], arr[b]
if a <= e1 and fn(va,vb) then
arr[pos] = va
a = a + 1
else
arr[pos] = vb
b = b + 1
end
pos = pos + 1
end
end
step = step * 2
end
return arr
end