Anybody interested in this sorting algorithm for lists?

[David Kastrup <dak at gnu dot org>]

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.

Attachment: lstest.cc
Description: Text document

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum