The Partition-Exchange Sort algorithm

The Partition-Exchange Sort algorithm

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

The basic idea is quite simple. Suppose that we have an array X
that is divided into two parts, A and B, and that A is sorted,
i.e. X = {A,B}. Select the midpoint of A and use it as a pivot
to partition A and B. Partition A requires no work; partitioning

B is O(N) time.

After partitioning the array looks like this: X = {A1,A2,B1,B2}
where A1 and B1 are the "small" components of the partitions and
A2 and B2 the "big"components. We swap segments A2 and B1 to get

X = {A1,B1,A2,B2}. This again is an O(N) time operation.

Now we apply the same procedure recursively to {A1,B1} and
{A2,B2} until the unsorted components are sorted. Since each
pass halves the component lengths there will be O(log N) passes.
As a result the over-all cost is O(N*log N) time. The space
requirement will be O(log N) because of the recursion.

There remains the question: How does A get sorted? That is
simple enough. We sort an a small initial segment and
successively double the initial segment size by applying the
partition-exchange algorithm.

An actual implementation requires handling some end cases. The
partition should take into account elements of B that are smaller

or larger than any element of A. The algorithm must account for
either B1 or B2 or both being empty. With this in mind the
partition is {B0,B1,B2,B3} where

B0 contains all elements less than all elements of A.
B1 contains all elements not in B0 that are less than the
pivot.
B2 contains all elements >= the pivot that are not greater
then all elements of A.
B3 contais all elements greater than all elements of A.

The algorithm then is:

if B0 has content then
swap A and B0
sort B0
if B1 has content then
swap A2 and B1
process {A1,B1}
if B2 has content then
process (A2,B2)
if B3 has content then
sort B3

Some interesting points about this algorithm are:

(a) It is a "good" sort algorithm, where "good" means that it has
an average O(N*log N) time cost and an average O(log N) space

cost.
(b) It has "good" worst behaviour; the key is that partitions
reduce segment sizes geometrically. It can be shown that the
worst case time and space costs are still O(N*log N) and
O(log N) respectively, assuming no error in my analysis.

(c) The size of the array does not need to be known in advance.
The implication is that it can be used for sorting input from
streams.

None of this means that this algorithm is more efficient than the

more well-known algorithms; it is quite likely that it isn't.
When I get the chance I will program a version and run some
tests.




Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

> 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.

On Mon, 28 Jul 2008 11:08:22 -0400, Chris F Clark
<cfc@shell01.TheWorld.com> 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).

Thank you for the comments.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

On Jul 28, 4:12*am, c...@tiac.net (Richard Harter) wrote:
> The Partition-Exchange Sort algorithm
>
> Partition-Exchange is a neologism; the algorithm discussed here
> may be novel. *In any event I haven't seen it before. *
>
> The basic idea is quite simple. *Suppose that we have an array X
> that is divided into two parts, A and B, and that A is sorted,
> i.e. *X = {A,B}. *Select the midpoint of A and use it as a pivot
> to partition A and B. *Partition A requires no work; partitioning
>
> B is O(N) time. *
>
> After partitioning the array looks like this: X = {A1,A2,B1,B2}
> where A1 and B1 are the "small" components of the partitions and
> A2 and B2 the "big"components. *We swap segments A2 and B1 to get
>
> X = {A1,B1,A2,B2}. *This again is an O(N) time operation.
>
> Now we apply the same procedure recursively to {A1,B1} and
> {A2,B2} until the unsorted components are sorted. *Since each
> pass halves the component lengths there will be O(log N) passes.
> As a result the over-all cost is O(N*log N) time. *The space
> requirement will be O(log N) because of the recursion.
>
> There remains the question: *How does A get sorted? *That is
> simple enough. *We sort an a small initial segment and
> successively double the initial segment size by applying the
> partition-exchange algorithm.
>
> An actual implementation requires handling some end cases. *The
> partition should take into account elements of B that are smaller
>
> or larger than any element of A. *The algorithm must account for
> either B1 or B2 or both being empty. *With this in mind the
> partition is {B0,B1,B2,B3} where
>
> * * B0 contains all elements less than all elements of A.
> * * B1 contains all elements not in B0 that are less than the
> * * * *pivot.
> * * B2 contains all elements >= the pivot that are not greater
> * * * *then all elements of A.
> * * B3 contais all elements greater than all elements of A.
>
> The algorithm then is:
>
> * * if B0 has content then
> * * * * swap A and B0
> * * * * sort B0
> * * if B1 has content then
> * * * * swap A2 and B1
> * * * * process {A1,B1}
> * * if B2 has content then
> * * * * process (A2,B2)
> * * if B3 has content then
> * * * * sort B3
>
> Some interesting points about this algorithm are:
>
> (a) It is a "good" sort algorithm, where "good" means that it has
> * * an average O(N*log N) time cost and an average O(log N) space
>
> * * cost.
> (b) It has "good" worst behaviour; the key is that partitions
> * * reduce segment sizes geometrically. *It can be shown that the
> * * worst case time and space costs are still O(N*log N) and
> * * O(log N) respectively, assuming no error in my analysis.
>
> (c) The size of the array does not need to be known in advance.
> * * The implication is that it can be used for sorting input from
> * * streams.
>
> None of this means that this algorithm is more efficient than the
>
> more well-known algorithms; it is quite likely that it isn't. *
> When I get the chance I will program a version and run some
> tests.
>
> Richard Harter, c...@tiac.nethttp://home.tiac.net/~cri,http://www.varinoma.com
> Save the Earth now!!
> It's the only planet with chocolate.

Richard,

This is very cool. Something like a cross-breeding of quicksort and
mergesort. I'm pretty sure it will not be fast, though. You'd like
to do the partition and exchange as elementwise "rotations", but you
can't because you don't know the sizes of b1 and b2 in advance.
Double handling for separate partition and exchange is expensive.

Oddly, a clean implementation may be possible for linked lists.

Gene

Gene wrote:
> On Jul 28, 4:12 am, c...@tiac.net (Richard Harter) wrote:
>> The Partition-Exchange Sort algorithm
>>
>> Partition-Exchange is a neologism; the algorithm discussed here
>> may be novel. In any event I haven't seen it before.
>>
>> The basic idea is quite simple. Suppose that we have an array X
>> that is divided into two parts, A and B, and that A is sorted,
>> i.e. X = {A,B}. Select the midpoint of A and use it as a pivot
>> to partition A and B. Partition A requires no work; partitioning
>>
>> B is O(N) time.
>>
>> After partitioning the array looks like this: X = {A1,A2,B1,B2}
>> where A1 and B1 are the "small" components of the partitions and
>> A2 and B2 the "big"components. We swap segments A2 and B1 to get
>>
>> X = {A1,B1,A2,B2}. This again is an O(N) time operation.
>>
>> Now we apply the same procedure recursively to {A1,B1} and
>> {A2,B2} until the unsorted components are sorted. Since each
>> pass halves the component lengths there will be O(log N) passes.
>> As a result the over-all cost is O(N*log N) time. The space
>> requirement will be O(log N) because of the recursion.
>>
>> There remains the question: How does A get sorted? That is
>> simple enough. We sort an a small initial segment and
>> successively double the initial segment size by applying the
>> partition-exchange algorithm.
>>
>> An actual implementation requires handling some end cases. The
>> partition should take into account elements of B that are smaller
>>
>> or larger than any element of A. The algorithm must account for
>> either B1 or B2 or both being empty. With this in mind the
>> partition is {B0,B1,B2,B3} where
>>
>> B0 contains all elements less than all elements of A.
>> B1 contains all elements not in B0 that are less than the
>> pivot.
>> B2 contains all elements >= the pivot that are not greater
>> then all elements of A.
>> B3 contais all elements greater than all elements of A.
>>
>> The algorithm then is:
>>
>> if B0 has content then
>> swap A and B0
>> sort B0
>> if B1 has content then
>> swap A2 and B1
>> process {A1,B1}
>> if B2 has content then
>> process (A2,B2)
>> if B3 has content then
>> sort B3
>>
>> Some interesting points about this algorithm are:
>>
>> (a) It is a "good" sort algorithm, where "good" means that it has
>> an average O(N*log N) time cost and an average O(log N) space
>>
>> cost.
>> (b) It has "good" worst behaviour; the key is that partitions
>> reduce segment sizes geometrically. It can be shown that the
>> worst case time and space costs are still O(N*log N) and
>> O(log N) respectively, assuming no error in my analysis.
>>
>> (c) The size of the array does not need to be known in advance.
>> The implication is that it can be used for sorting input from
>> streams.
>>
>> None of this means that this algorithm is more efficient than the
>>
>> more well-known algorithms; it is quite likely that it isn't.
>> When I get the chance I will program a version and run some
>> tests.
>>
>> Richard Harter, c...@tiac.nethttp://home.tiac.net/~cri,http://www.varinoma.com
>> Save the Earth now!!
>> It's the only planet with chocolate.
>
> Richard,
>
> This is very cool. Something like a cross-breeding of quicksort and
> mergesort. I'm pretty sure it will not be fast, though. You'd like
> to do the partition and exchange as elementwise "rotations", but you
> can't because you don't know the sizes of b1 and b2 in advance.
> Double handling for separate partition and exchange is expensive.
>
> Oddly, a clean implementation may be possible for linked lists.

I think it would be difficult to come up with an algorithm
that was more naturally suited to linked lists,
than mergesort already is.

--
pete

On Tue, 29 Jul 2008 07:35:40 -0400, pete <pfiland@mindspring.com>
wrote:

>Gene wrote:
>> On Jul 28, 4:12 am, c...@tiac.net (Richard Harter) wrote:

[snip algorithm]

>>
>> Richard,
>>
>> This is very cool. Something like a cross-breeding of quicksort and
>> mergesort. I'm pretty sure it will not be fast, though. You'd like
>> to do the partition and exchange as elementwise "rotations", but you
>> can't because you don't know the sizes of b1 and b2 in advance.
>> Double handling for separate partition and exchange is expensive.

Thanks, I thought it was cool too. I came up with it when I was
thinking about ways to do in place merges.

You're probably right about the speed, though the exchange cost
should be relatively low compared to the partition cost. The
swaps can be done using buffered block copies; most systems can
do high speed block moves.

Still, it might be fast enough to be useful when you want a good
worst case comparison sort. The principle candidate here is
heapsort, and it has locality problems.


>>
>> Oddly, a clean implementation may be possible for linked lists.
>
>I think it would be difficult to come up with an algorithm
>that was more naturally suited to linked lists,
>than mergesort already is.

I'm not sure what you mean by that. Quicksort works rather
nicely with linked lists.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

On Jul 29, 11:13*am, c...@tiac.net (Richard Harter) wrote:
> On Tue, 29 Jul 2008 07:35:40 -0400, pete <pfil...@mindspring.com>
> wrote:
>
> >Gene wrote:
> >> On Jul 28, 4:12 am, c...@tiac.net (Richard Harter) wrote:
>
> [snip algorithm]
>
>
>
> >> Richard,
>
> >> This is very cool. *Something like a cross-breeding of quicksort and
> >> mergesort. *I'm pretty sure it will not be fast, though. *You'd like
> >> to do the partition and exchange as elementwise "rotations", but you
> >> can't because you don't know the sizes of b1 and b2 in advance.
> >> Double handling for separate partition and exchange is expensive.
>
> Thanks, I thought it was cool too. *I came up with it when I was
> thinking about ways to do in place merges.
>
> You're probably right about the speed, though the exchange cost
> should be relatively low compared to the partition cost. *The
> swaps can be done using buffered block copies; most systems can
> do high speed block moves.
>
> Still, it might be fast enough to be useful when you want a good
> worst case comparison sort. *The principle candidate here is
> heapsort, and it has locality problems.
>
>
>
> >> Oddly, a clean implementation may be possible for linked lists.
>
> >I think it would be difficult to come up with an algorithm
> >that was more naturally suited to linked lists,
> >than mergesort already is.
>
> I'm not sure what you mean by that. *Quicksort works rather
> nicely with linked lists.

Yes it does! When I've benchmarked, though, the mergesort always
seems to do better by a significant factor, at least when the
comparison cost is comparable to link munging.

On Tue, 29 Jul 2008 10:32:20 -0700 (PDT), Gene
<gene.ressler@gmail.com> wrote:

>On Jul 29, 11:13=A0am, c...@tiac.net (Richard Harter) wrote:
>> On Tue, 29 Jul 2008 07:35:40 -0400, pete <pfil...@mindspring.com>
>> wrote:
>>
>> >Gene wrote:
>> >> On Jul 28, 4:12 am, c...@tiac.net (Richard Harter) wrote:
>>
>> [snip algorithm]
>>
>>
>>
>> >> Richard,
>>
>> >> This is very cool. =A0Something like a cross-breeding of quicksort and
>> >> mergesort. =A0I'm pretty sure it will not be fast, though. =A0You'd li=
>ke
>> >> to do the partition and exchange as elementwise "rotations", but you
>> >> can't because you don't know the sizes of b1 and b2 in advance.
>> >> Double handling for separate partition and exchange is expensive.
>>
>> Thanks, I thought it was cool too. =A0I came up with it when I was
>> thinking about ways to do in place merges.
>>
>> You're probably right about the speed, though the exchange cost
>> should be relatively low compared to the partition cost. =A0The
>> swaps can be done using buffered block copies; most systems can
>> do high speed block moves.
>>
>> Still, it might be fast enough to be useful when you want a good
>> worst case comparison sort. =A0The principle candidate here is
>> heapsort, and it has locality problems.
>>
>>
>>
>> >> Oddly, a clean implementation may be possible for linked lists.
>>
>> >I think it would be difficult to come up with an algorithm
>> >that was more naturally suited to linked lists,
>> >than mergesort already is.
>>
>> I'm not sure what you mean by that. =A0Quicksort works rather
>> nicely with linked lists.
>
>Yes it does! When I've benchmarked, though, the mergesort always
>seems to do better by a significant factor, at least when the
>comparison cost is comparable to link munging.

By about 20% I would imagine. The best possible comparison sort
requires ~ log2(n)-log2(e) comparisons per element. If I recall
correctly mergesort requires ~log2(n)-1 comparisons per element
whereas quicksort requires ~ 1.22*log2(n) comparisons per
element.



Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

What is the difference between your Partition-Exchange Sort algorithm
and Chen's Proportion Extend Sort algorithm?

On Tue, 29 Jul 2008 16:49:23 -0700 (PDT), zxcb33@yahoo.com wrote:

>What is the difference between your Partition-Exchange Sort algorithm
>and Chen's Proportion Extend Sort algorithm?

Good question; thanks for the alert. I hadn't heard of Chen's
work before, which is not surprising since it appears to be
relatively new. At first glance the key idea is the same. I'm
not sure that he used the same strategy for outliers.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.