Fusion Sort?

[swestrup]

Years ago (probably over 10), I heard about a new sort algorithm that was supposed to be faster than quicksort, on the sort of data that quicksort handles best, but only for very large sorts (10s of millions of items or more).

The algorithm was called, IIRC, "Fusion Sort" and was supposed to do three-way tests, with different behavious for less, greater and equal. This gave a marginally better sort for very long runs, and a marginally worse sort for anything smaller. At the time of the announcement, the algorithm had been accepted by some journal or other, and had not yet been published, so they couldn't give any more details.

Other than that one news article, I have never heard another thing about this sort, and searches for "Fusion Sort" turn up nothing. Does this ring any bells with anyone? I would like to know if this algorithm exists, what it is currently called if it does, or was it discredited soon after publication?

Comments

[skjalm.livejournal.com]

This is just an off-the-top-of-my-head thought:
http://www4.in.tum.de/~webertj/publications/quicksort-via-birds-tree-fusion-transformation.html

Doesn't seem to be exactly what you describe - I just remembered I had seen something with "fusion" and "sorting" not too long ago. Good luck with finding the algorithm.

Hope you don't mind me adding you. You sound like an interesting person so I couldn't resist ;-)

[swestrup]

No problem. I asked on algorithms and they had a useful pointer.

[swestrup]

Oh, and welcome. :-)