--- Begin Message ---
- From: David Kastrup <dak at gnu dot org>
- To: Dhruv Matani <dhruvbird at gmx dot net>
- Date: 24 Jul 2004 09:34:29 +0200
- Subject: Re: Anybody interested in this sorting algorithm for lists?
- References: <x51xj2ppuo.fsf@lola.goethe.zz><1090637475.3056.18.camel@localhost.localdomain>
Dhruv Matani <dhruvbird@gmx.net> writes:
> This looks really good!
>
> Have you documented the algorithm, because I would be interested in
> knowing what exactly it does!
Actually, this is a spinoff from the C version extracted from
<URL:http://cvs.sourceforge.net/viewcvs.py/*checkout*/preview-latex/preview/lib/listsort.tex>
and documented there, more or less. It is a merge sort that merges
partial lists as soon as they become available and finds the start of
the next sublist "on the fly" while sorting the previous one. The
control logic does not work by actually doing recursive calls, but
instead by looking at bit patterns from connected arithmetic. Reading
tea leaves, so to say. The result is strictly the same as splitting
the list in two equally large parts, sorting the parts recursively,
and then merging them.
It is just wrapped in C++-ese, and this was the first time that I
managed to wrap it in C++ that actually would compile (I tried over
the last decade or so sometimes to get a version that would be useful
C++ and compile under current gcc versions). Actually, just having
upgraded to gcc-3.4.1, my current version stopped compiling again, but
the fix is trivial: just make the constructors of sorter and sorter2
public, and remove the friend-declarations.
It is a pity the helper classes can't be placed local to the template
sort functions: one would probably want to use some "sortinternals"
namespace or so to hide them away.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
--- End Message ---