Listing 2: Implementation of qsortVT and qsortPT

// Listing 2: qsortT.cpp
#include <assert.h>
template<class T> void qsortVT(T *data, const int num)
{
#define SMALLEST_PARTITION 15
    register int i, j;
    int first,
        last,
        stack_pointer;
    T temp;
    struct
    {
        int left,
            right;
    } stack[100];

    if (num <= 0)
        return;
    stack_pointer = 0;
    stack[0].left = 0;
    stack[0].right = num-1;
    while (stack_pointer >= 0)
    {
        first = stack[stack_pointer].left;
        last  = stack[stack_pointer].right;
        assert(first >= 0);
        assert(last >= 0);
        assert(first < num);
        assert(last < num);
        stack_pointer--;

        temp = data[first];
        data[first] = data[(last + first) / 2];
        data[(last + first) / 2] = temp;

        i = first + 1;
        j = last;
        while (i <= j)
        {
            while (data[i]==data[first] || data[i]<data[first])
            {
                if (++i > last)
                    break;
            }
            while (! (data[j] < data[first]))
            {
                if (--j <= first)
                    break;
            }
            if (j > i)
            {
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }

        temp = data[first];
        data[first] = data[j];
        data[j] = temp;

        if ((j - first) >= SMALLEST_PARTITION)
        {
            stack[++stack_pointer].left = first;
            stack[stack_pointer].right = j - 1;
        }
        if ((last - j) >= SMALLEST_PARTITION)
        {
            stack[++stack_pointer].left = j + 1;
            stack[stack_pointer].right = last;
        }
    }

    for (i = 1; i < num; i++)
    {
        temp = data[i];
        j = i - 1;
        while (j >= 0)
        {
            if ( (! (data[j] == temp)) && (! (data[j] < temp)))
            {
                data[j+1] = data[j];
                j--;
            }
            else
                break;
        }
        data[j+1] = temp;
    }
}

template<class T> void qsortPT(T **data, const int num)
{
#define SMALLEST_PARTITION 15
    register int i, j;
    int first,
        last,
        stack_pointer;
    T *temp;
    struct
    {
        int left,
            right;
    } stack[100];

    if (num <= 0)
        return;
    stack_pointer = 0;
    stack[0].left = 0;
    stack[0].right = num-1;

    while (stack_pointer >= 0)
    {
        first = stack[stack_pointer].left;
        last  = stack[stack_pointer].right;
        assert(first >= 0);
        assert(last >= 0);
        assert(first < num);
        assert(last < num);
        stack_pointer--;

        temp = data[first];
        data[first] = data[(last + first) / 2];
        data[(last + first) / 2] = temp;

        i = first + 1;
        j = last;
        while (i <= j)
        {
            while (*data[i]==*data[first]||*data[i]<*data[first])
            {
                if (++i > last)
                    break;
            }
            while (! (*data[j] < *data[first]))
            {
                if (--j <= first)
                    break;
            }
            if (j > i)
            {
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }

        temp = data[first];
        data[first] = data[j];
        data[j] = temp;

        if ((j - first) >= SMALLEST_PARTITION)
        {
            stack[++stack_pointer].left = first;
            stack[stack_pointer].right = j - 1;
        }
        if ((last - j) >= SMALLEST_PARTITION)
        {
            stack[++stack_pointer].left = j + 1;
            stack[stack_pointer].right = last;
        }
    }

    for (i = 1; i < num; i++)
    {
        temp = data[i];
        j = i - 1;
        while (j >= 0)
        {
            if ( (! (*data[j]==*temp)) && (! (*data[j]<*temp)))
            {
                data[j+1] = data[j];
                j--;
            }
            else
                break;
        }
        data[j+1] = temp;
    }
}

// End of Listing 2