Re: Stable sort for Lua 4.1?

[Roberto Ierusalimschy <roberto@...>]

About mergesort x quicksort:

> 1. It's simpler (which although it's not of interest to the user, may be to
> the Lua developers). For example, it could be implemented non-recursively,
> thus improving memory requirements (the current Quicksort is recursive,
> though only on the smaller partition).

That would be a big plus, if it reflects in implementation size. The
recursiveness of quicksort doesn't seem to be a problem, as it needs at
most twenty levels (less than 1Kbyte of stack) to sort 10^6 elements.


> 2. It's guaranteed best case (O(NlogN), although the constant factor may be
> higher than for quicksort; [...]

That would need some testing. Moving elements is also critical in Lua.


Why don't you try? If the result is smaller than the current implementation 
(quite probable) and with a comparable performance, we can adopt it. (I 
would even accept a small performance penalty for a smaller and stable 
algorithm.)  (Just in case, I am sending attached the standard tests for
sorting in Lua.)

-- Roberto

PS:
> You can also find versions of Mergesort which have a linear best-case time,
Where?

print"verificando sort"


function check (a, f)
  f = f or function (x,y) return x<y end;
  for n=getn(a),2,-1 do
    assert(not f(a[n], a[n-1]))
  end
end

a = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep",
     "Oct", "Nov", "Dec"}

sort(a)
check(a)

limit = 30000
if _soft then limit = 5000 end

a = {}
for i=1,limit do
  a[i] = random()
end

local x = clock()
sort(a)
print(format("Sorting %d elements in %.2f sec.", limit, clock()-x))
check(a)

x = clock()
sort(a)
print(format("Re-sorting %d elements in %.2f sec.", limit, clock()-x))
check(a)

a = {}
for i=1,limit do
  a[i] = random()
end

x = clock(); i=0
sort(a, function(x,y) i=i+1; return y<x end)
print(format("Invert-sorting other %d elements in %.2f sec., with %i comparisons",
      limit, clock()-x, i))
check(a, function(x,y) return y<x end)


sort{}  -- array vazio

a.n = 2
sort(a)  -- so' 2 primeiros elementos
assert(a[1] <= a[2] and a.n == 2)
for i=3,limit-1 do
  assert(a[i] >= a[i+1])
end

a = {n=limit}
x = clock();
sort(a, function(x,y) return nil end)
print(format("Sorting %d equal elements in %.2f sec.", limit, clock()-x))
check(a, function(x,y) return nil end)
for i,v in a do assert (i=='n' and v==limit) end

a = {"álo", "\0first :-)", "alo", "then this one", "45", "and a new"}
sort(a)
check(a)

sort(a, function (x, y)
          dostring(format("a[%q] = ''", x))
          collectgarbage()
          return x<y
        end)


tt = newtag()
a = {}
for i=1,10 do  a[i] = {val=random(100)}; settag(a[i], tt); end
f = function (a,b) return a.val < b.val end
settagmethod(tt, 'lt', f)
sort(a)
check(a, f)

print"OK"