Re: A stable sort

[Eike Decker <zet23t@...>]

2013/5/3 S. Fisher <expandafter@yahoo.com>

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:

--- 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

a = a + 1

else

arr[pos] = vb

b = b + 1

end

pos = pos + 1

end

end

step = step * 2

end

return arr

end