"Быстрая" сортировка работает в среднем за время O ( n*log(n) ), а в худшем случае за O ( n² ), но в отличии от сортировки слиянием не требует дополнительного массива. Здесь эта сортировка представлена в виде двух шаблонов. Первый шаблон quickSort123 сортируют элементы массивов по возрастанию:

template <class T> ArrRef<T> quickSort123 ( ArrRef<T> & a )
{
    const nat n = a.size();
    if ( n < 2 ) return a;
    const nat small_size = sizeof(T) > 8 ? 24 : sizeof(T) > 4 ? 40 : 48;
    CmbSuite<T*, 64> buf;
    T * lo = a();
    T * hi = lo + ( n - 1 );
m1:
    nat size = ( hi - lo ) + 1;
    if ( size <= small_size )
    {
        insertSort123 ( ArrRef<T> ( a, lo - a(), size ) );
    }
    else
    {
        T * mid = lo + ( size / 2 );
        _swap ( *mid, *lo );
        T * lo1 = lo;
        T * hi1 = hi + 1;
        for (;;)
        {
            do
            {
                lo1 += 1;
            }
            while (lo1 <= hi && *lo1 <= *lo );

            do
            {
                hi1 -= 1;
            }
            while ( hi1 > lo && *hi1 >= *lo );

            if ( hi1 < lo1 )
                break;

            _swap ( *lo1, *hi1 );
        }
        _swap ( *lo, *hi1 );
        if ( hi1 - 1 - lo >= hi - lo1 )
        {
            if ( lo + 1 < hi1 )
            {
                buf.inc() = lo;
                buf.inc() = hi1 - 1;
            }

            if ( lo1 < hi )
            {
                lo = lo1;
                goto m1;
            }
        }
        else
        {
            if ( lo1 < hi )
            {
                buf.inc() = lo1;
                buf.inc() = hi;
            }

            if ( lo + 1 < hi1 )
            {
                hi = hi1 - 1;
                goto m1;
            }
        }
    }
    if ( buf.size() > 0 )
    {
        lo = buf.las(1);
        hi = buf.las(0);
        buf.dec(2);
        goto m1;
    }
    return a;
}

Второй шаблон quickSort321 сортируют элементы массивов по убыванию и устроен аналогично.
Описание шаблонов классов ArrRef и CmbSuite находится здесь.

Исходники находятся в файле func1t.h.