For what it worth, here is a qsort from our project. (I'd better give a
link but sourceforge site is down these days).
-- qsort [ extracted from Lua 5.1 distribution (file /test/sort.lua) ]
local function qsort(x,l,u,sz,f)
x = ffi.cast("char*",x)
local v = ffi.new("char[?]",sz)
local function swap(i1,i2)
i1, i2 = x+i1*sz, x+i2*sz
ffi.copy(v,i1,sz); ffi.copy(i1,i2,sz); ffi.copy(i2,v,sz)
end
local function recurse(l,u)
if l<u then
local m=math.random(u-(l-1))+l-1 -- choose a random pivot in
range l..u
swap(l,m) -- swap pivot to first position
local t=x+l*sz -- pivot value
m=l
for i=l+1, u do
-- invariant: x[l+1..m] < t <= x[m+1..i-1]
if f(x+i*sz, t) then
m = m+1
swap(m,i) -- swap x[i] and x[m]
end
end
swap(l,m) -- swap pivot to a valid place
-- x[l+1..m-1] < x[m] <= x[m+1..u]
recurse(l, m-1)
recurse(m+1, u)
end
end
recurse(l,u)
end
--
Shmuel
