timesort.cc  From Astrachan pp 544-546
--------------------------------------
#include <iostream.h>
#include "ctimer.h"
#include "vector.h"
#include "rando.h"

// Owen Astrachan, 7/30/95
// time sorts, compare quick sort and selection sort

template <class Type>
void Swap(Type & a, Type & b)
// generic swap routine     
{
    Type temp;
    temp = a;
    a = b;
    b = temp;
}

template <class Type>
int Pivot(Vector<Type> & a,int first,int last)
// postcondition: returns piv such that
//                first <= k <= piv, a[k] <= a[piv]
//                piv < k <= last, a[piv] < a[k]                
// (from Bently, programming Pearls)
{
    int k,p=first;
    Type piv;
    
    piv = a[first];                    // first element is pivot
    
    for(k=first+1; k <= last; k++)
    {
        if (a[k] <= piv)               // belongs in first "half"
        {
            p++;                       // p now indexes "greater" element
            Swap(a[k],a[p]);           // swap smaller and greater!
        }
    }
    Swap(a[p],a[first]);               // put pivot in proper location
    return p;
}

template <class Type>
void Quick(Vector<Type> & a,int first,int last)
// postcondition: a[first] <= ... <= a[list]     
{
    int piv;
    
    if (first < last)
    {
        piv = Pivot(a,first,last);    // find pivot and divide vector
        Quick(a,first,piv-1);         // sort first "half"
        Quick(a,piv+1,last);          // sort other  half
    }
}

template <class Type>
void QuickSort(Vector<Type> & a, int size)
// precondition: size = # of elements of a
// postcondition: a is sorted     
{
    Quick(a,0,size - 1);
}

template <class Type>
void SelectSort(Vector<Type> & a, int numElts)
// precondition: a contains numElts elements
// postcondition: elements of a are sorted in non-decreasing order
{
    int j,k,minIndex;

    for(k=0; k < numElts - 1; k++)
    {
        minIndex = k;                 // smallest item from k to end of a
        for(j=k+1; j < numElts; j++)
        {
            if (a[j] < a[minIndex])
            {
                minIndex = j;         // new smallest item, remember where
            }
        }
        Swap(a[k],a[minIndex]);       // swap smallest item and k-th item
    }
}

void Load(Vector<int> & a, int numElts)
// precondition: numElts <= a.Length()
// postcondition: 0 <= a[k] = random integer <= INT_MAX
{
    int k;
    RandGen rando;

    for(k=0; k < numElts; k++)
    {
        a[k] = rando.RandInt();
    }
}

int main()
{
    Vector<int> list;        // stores numbers to sort
    int minSize,maxSize;     // size range of vector
    int incr;                // increment between sizes
    CTimer timer;    
    int trials;              // number of sorting trials
    int size,k;

    cout << "min and max size of vector: ";
    cin >> minSize >> maxSize;

    cout << "increment of size for each sort: ";
    cin >> incr;

    cout << "number of trials: ";
    cin >> trials;

    for(size=minSize; size <= maxSize; size += incr)
    {
        list.SetSize(size);

        for(k=0; k < trials; k++)
        {
            Load(list,size);
            timer.Start();
            QuickSort(list,size);
            timer.Stop();
        }
        cout << "size = " << size;
        cout << "  time = " << timer.CumulativeTime()/trials << endl;
    }
    return 0;
}