Re: The Partition-Exchange Sort algorithm

cri@xxxxxxxx (Richard Harter) writes:

On Mon, 28 Jul 2008 11:08:22 -0400, Chris F Clark
<cfc@xxxxxxxxxxxxxxxxxxxx> wrote:

Partition-Exchange is a neologism; the algorithm discussed here
may be novel. In any event I haven't seen it before.

The idea has some merits. However, there is only a minimal guarantee
that the sizes of the B's relative to the A's are anywhere close in
size. You talk to that problem in your issues to resolve, but the
worst case looks easily to be some kind of situation when the pivot
you pick sorts all of the B's the the one side and that happens
repetitively, for example how does your algorithm perform on a
completely reversed list.


How does it perform on a completely reversed list? Quite well
indeed, thank you. :-)

You are right, of course, that the sizes of the B's can differ
significantly from the sizes of the A's, but this is a
self-correcting problem. The essence of the matter is that
partitioning of B removes all values within B that are outside of
the box defined by A and treats them as sub-problems. For
example, a reversed list is handled by sorting the first half,
swapping the first and second halves, and then sorting the new
first half.

The problem occurs when all of the B's stay within range. The
worst case is when all of the B's lie between a successive pair
of A's. In such case we must perform log n partitions to find a
new subproblem. The worst case happens when this feature is
present recursively in the data. In such case the time cost is
O(n * (log n)^2).

This Partition-Exchange sort idea was interesting. I tried coding it
up, and it wasn't too bad. It's a little bit sad that its worst case
is slower than O(n * log n).

After playing around with it a bit, I came up with another sorting
algorithm that I thought was pretty neat. Worst case comparison cost
of n * log2 n (that is, the constant is 1), and the move cost is also
O(n * log n) with a fairly small constant. Of course, it turns out
someone else had already thought of it:

Practical In-Place Mergesort
http://www.diku.dk/~jyrki/Paper/mergesort_NJC.ps

I like this algorithm. It's easy to understand, fairly easy to
code up, and has excellent worst-case behavior for comparisons,
and pretty good worst-case behavior for movement. I haven't
actually measured it but it looks like the locality is not
bad, and in particular looks better than Heapsort.
.