outline-style sorting algorithm

[Delaney, Timothy C (Timothy)]

Thorsten Kampe wrote:

> You DSU approach took about 43 s and mine took about 86 s.
> Than I tested range(1000000) in reverse order:
> Your sorted program took about 24 s and mine about 5!

I've taken the code that you posted in response to Terry, fixed it
(there were some extra parentheses and I don't have the `colour`
module). I didn't modify any of the functions.

Windows XP SP1
P4 3GHz (HT enabled)
Python 2.3.3

a = range(1000000); a.reverse()
b = randseq(1, 1000000, 1000000, 'repeat')

cpu: 3.610, total: 3.609    # timer(funcsort, a, lambda x: x, 'dsu')
cpu: 1.387, total: 1.390    # timer(funcsort, a, lambda x: x, 'pass')
cpu: 9.050, total: 9.047    # timer(funcsort, b, lambda x: x, 'dsu')
cpu: 26.459, total: 26.469  # timer(funcsort, b, lambda x: x, 'pass')

These results are in stark contrast to yours. What version of Python
were you using?

> So you cannot simply state that DSU is faster than passing a function
> if the structure of the input you want to sort is unknown...

That's why I said "almost all cases preferred". In the first run above,
it's obvious that the additional overhead of generating the keys, etc
exceeds the time spent comparing. Most likely because the 2.3 sort is
very efficient for partially-ordered lists (like a reversed list) and
therefore the comparison function doesn't get called many times.

Now, when randomness is introduced the comparison function ends up being
called a lot more and it's overhead is far greater than with DSU.

Tim Delaney