Anybody interested in this sorting algorithm for lists?

[David Kastrup]

Hi,

the below sorting algorithm benchmarks almost twice as fast as that
included in the STL, but since it accesses link fields directly, it
needs to be a member function of the list classes from STL in order to
be used with STL; and at the end of the sorting, one would need a
single pass through the list in order to reconstitute the backward
links properly.  It sorts stably, needs no recursion (well, it uses an
internal stack chosen large enough to sort size_t elements), no
additional memory, is strictly O(n log n) yadda yadda yadda.  It would
probably make sense to provide the core sorting routine as a separate
building block, but that would be a bit out of STL proper then.

I have not written a copyright assignment to whatever it would take to
put stuff in libstdc++, but have gone through that procedure for a few
other projects.

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: lstest.cc
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040723/52fb3a02/attachment.cc>
-------------- next part --------------


-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum