Fastest sort algorithm?

[Richard Cavell]

Hi,

I have a structure of 3 16-bit values. I have either 65000, 256000 or 1
million instances of this structure. I want to sort the lot of them
according to the number contained in one of the fields. Duplicate
values are allowed. So obviously if many instances of the structure
have the same value in this field, they must be together but they can be
in any order. The instances are already weakly sorted.

On modern Pentium 4/Athlon/G5, what would be the fastest algorithm to
use, and does anyone have any pointers to a fast implementation?

[REH]

"Richard Cavell" <ri***********@mail.com> wrote in message
news:d2*********@nnrp.waia.asn.au...

Hi,

I have a structure of 3 16-bit values. I have either 65000, 256000 or 1
million instances of this structure. I want to sort the lot of them
according to the number contained in one of the fields. Duplicate
values are allowed. So obviously if many instances of the structure
have the same value in this field, they must be together but they can be
in any order. The instances are already weakly sorted.

On modern Pentium 4/Athlon/G5, what would be the fastest algorithm to
use, and does anyone have any pointers to a fast implementation?

This is OT, but I'll try and help. You data set is probably prohibitively
large for all O(n) sort except for the Radix sort. I would also look at the
introspection sort (O(n log n)). How sorted is your weakly sorted data?
There are sorts that are or approach O(n) if the data is close to being
already sorted.

I have C++ implementation of many sorts, including three O(n) sorts, but not
here at work. If you like, I can email them to you this evening.

REH

[Richard Cavell]

On 1/4/05 12:48 AM, REH wrote:

This is OT, but I'll try and help. You data set is probably prohibitively
large for all O(n) sort except for the Radix sort. I would also look at the
introspection sort (O(n log n)). How sorted is your weakly sorted data?
My data looks like a sawtooth waveform when graphed out (not perfectly
so, but definitely that sort of shape). I'm trying to get it into a
perfect ramp.
I have C++ implementation of many sorts, including three O(n) sorts, but not
here at work. If you like, I can email them to you this evening.

Yes please.

[REH]

"Richard Cavell" <ri***********@mail.com> wrote in message
news:d2**********@nnrp.waia.asn.au...

On 1/4/05 12:48 AM, REH wrote:

This is OT, but I'll try and help. You data set is probably prohibitively large for all O(n) sort except for the Radix sort. I would also look at the introspection sort (O(n log n)). How sorted is your weakly sorted data?

My data looks like a sawtooth waveform when graphed out (not perfectly
so, but definitely that sort of shape). I'm trying to get it into a
perfect ramp.

I have C++ implementation of many sorts, including three O(n) sorts, but not here at work. If you like, I can email them to you this evening.

Yes please.

I didn't see your reply until I got to work this morning, so I'll send them
this evening. Each sort is encapsulated in a class, with traits that
defines such things as its performance, stability, in-place sorting, etc.
This is also a test program that times each sort and records the number of
swaps and compares (if appl.).

REH