Re: A stable sort

[Eike Decker <zet23t@...>]

2013/5/8 Dirk Laurie <dirk.laurie@gmail.com>

2013/5/8 Eike Decker <zet23t@googlemail.com>:

>> I only wrote this quickly and haven't given it intensive testing, but this
>> sort function is pretty simple, short, stable and fast

And wrong.

         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

Say on the first iteration you take the "else" branch. It stores `vb`
in `arr[pos]` which is `arr[a]`. So `arr[a]` is now clobbered. It
still sits in `va` but `va` is not used again.

You can postpone the inevitable by:

         local pos, va, vb = a, arr[a], arr[b]

         while a <= e1 and b <= e2 do

            if a <= e1 and fn(va,vb) then
               arr[pos] = va
               a = a + 1

               va = arr[a]

            else
               arr[pos] = vb
               b = b + 1

               vb = arr[b]

            end
            pos = pos + 1
         end

Now you need to take the "else" branch twice in a row before
something goes wrong.

There are in-place merge sorts around but they are not this simple.

Yupp, should do more testing. But the algorithm was in my head but I forgot it won't work inplace - and it's certainly not trivial. 

I fixed the version and it now uses a swap table of same size as the input table. It's sadly now a bit more complex, though that is due to the fact that I had to optimize it - otherwise it would have been slower than Fisher's version. It avoids recursions and function calls and the calculations are pretty simple since the step size is predetermined. It's about 20% faster than Fisher's version and hopefully without bugs (won't rule it out though. I think a native C implementation would be pretty straight forward and fast. 

Oh, and about stable sorting in general, I am in line with Fisher's opinion. The _javascript_, the spec doesn't demand the sorting to be stable. Firefox sorts stable, chrome doesn't. You can guess the fun...

here's the fixed function:

--- 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(arr, goes_before)

local n = #arr

local step = 1

local fn = goes_before or function(a,b) return a < b end

local tab1,tab2 = arr, {}

-- tab1 is sorted in buckets of size=step

-- tab2 will be sorted in buckets of size=step*2

while step < n do

for i=1,n,step*2 do

-- for each bucket of size=step, merge the results

local pos,a,b = i, i, i + step

local e1,e2 = b-1, b+step-1

-- e1= end of first bucket, e2= end of second bucket

if e1 >= n then 

-- end of our array, just copy the sorted remainder

while a <= e1 do 

tab2[a],a = tab1[a], a+1

end

break 

elseif 

e2 > n then e2 = n 

end

-- merge the buckets

while true do

local va,vb = tab1[a], tab1[b]

if fn(va,vb) then

tab2[pos] = va

a = a + 1

if a > e1 then 

-- first bucket is done, append the remainder

pos = pos + 1

while b <= e2 do tab2[pos],b,pos = tab1[b], b + 1,pos+1 end

break 

end

else

tab2[pos] = vb

b = b + 1

if b > e2 then

-- second bucket is done, append the remainder

pos = pos + 1

while a <= e1 do tab2[pos],a,pos = tab1[a], a + 1,pos+1 end

break

end

end

pos = pos + 1

end

end

step = step * 2

tab1,tab2 = tab2,tab1

end

-- copy sorted result from temporary table to input table if needed

if tab1~=arr then 

for i=1,n do arr[i] = tab1[i] end 

end

return arr

end