template <typename T>
void qsort (T *result, T *list, int n)
{
    if (n == 0) return;
    T *smallerList, *largerList;
    smallerList = new T[n];
    largerList = new T[n];
    T pivot = list[0];
    int numSmaller=0, numLarger=0;
    for (int i = 1; i < n; i++)
        if (list[i] < pivot)
            smallerList[numSmaller++] = list[i];
        else
            largerList[numLarger++] = list[i];

    qsort(smallerList,smallerList,numSmaller);
    qsort(largerList,largerList,numLarger);

    int pos = 0;
    for ( int i = 0; i < numSmaller; i++)
        result[pos++] = smallerList[i];

    result[pos++] = pivot;

    for ( int i = 0; i < numLarger; i++)
        result[pos++] = largerList[i];

    delete [] smallerList;
    delete [] largerList;
};