lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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
arr[pos] = vb
b = b + 1
pos = pos + 1
step = step * 2
return arr