[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: A stable sort**
**From**: Dirk Laurie <dirk.laurie@...>
**Date**: Wed, 8 May 2013 16:06:24 +0200

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.