Hi.
DN> Here is the template for Quicksort with 2 refinements over Hoare's 
DN> original algorithm:
DN>      i)  Use of Insertion sort for subfiles shorter than a threshold;
DN>     ii)  Singleton's median-of-three pivot selection.
DN> 
DN> I have also changed the placeholder for the pivot element from a 
DN> subscript to a pointer. This will produce slightly better code on most 
DN> 16-bit systems, and from some 32-bit compilers too.
DN> 
As you seem to like sort-algorithms here I've got straight 2-way mergesort 
for you.
DN>After that, I will post a benchmark program, possibly a few, that will
DN>attempt to show each algorithm in its best and worst lights.
Could you test my mergesort-algorithms, too? I know that they are O(N log N) 
but I don't know how fast they really are.
============================ mergesrt.hpp ================================== 
// ascending & descending straight 2-way mergesort.
// Copyright (C) 1998, Dominic Battre
// All rights reserved.
// You can copy and use this code freely - all you have to do is to keep my
// name in it.
#if !defined(MERGESRT_H)
#define MERGESRT_H
#define maxSize 5000
template  void ascending(T array[], int l, int r) {
  int i, j, k, m;
  T array2[maxSize];
  if (r > l) {
    m = (r+l)/2;
    ascending(array, l, m);
    ascending(array, m+1, r);
    for (i = m+1; i > l; i--) array2[i-1] = array[i-1];
    for (j = m; j l) {
    m = (r+l)/2;
    descending(array, l, m);
    descending(array, m+1, r);
    for (i = m+1; i > l; i--) array2[i-1] = array[i-1];
    for (j = m; j array2[j])?array2[i++]:array2[j--];
  }
}
#endif
Domi
Ausgezeichnet mit dem Funstar:
http://home.t-online.de/home/D_Battre
--- FIPS/32 v0.99b W95/NT [M]
---------------