template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
int randint(int l, int u) {
    srand(time(NULL));
    return l + rand() % (u-l + 1);
}
 
const int cutoff = 5;
template<class T>
void QSort4(T* x, int l, int u) {
    if (u - l < cutoff)
        return;
 
    swap(x, l, randint(l, u));
    T t;
    int i,j;
    t = x[l]; i = l; j = u+1;
 
    while (1) {
        /* пропуск элементов справа и слева,
           чтобы не делать лишней работы */
        do i++; while (i <= u && x[i] < t);
        do j--; while (x[j] > t);
 
        if (i > j)
            break;
        // Делаем swap(i, j):
        T tmp;
        tmp = x[i]; x[i] = x[j]; x[j] = tmp;
    }
 
    swap(x, l, j);
 
 
    QSort4(x, l, j-1);
    QSort4(x, j+1, u);
}

Быстрая сортировка с двусторонним алгоритмом разбиения + случайным выбором элемента разбиения + запретом сортировок малых подмножеств, на которые тратится больше всего времени.

Индексы i и j инициализируются граничными индексами разбиваемого массива. Главный цикл содержит два вложенных цикла. Первый вложенный цикл сдвигает i вверх, пропуская меньшие элементы, а второй увеличивает j, пропуская большие элементы и останавливаясь на меньшем. Главный цикл проверяет, не пересекаются ли эти индексы, и переставляет соответствующие элементы.

cutoff — некоторое небольшое целое число. После завершения работы функции массив будет не отсортирован до конца, но разбит на небольшие группы случайно упорядоченных элементов, причем все элементы одной группы будут меньше любого элемента всех групп, расположенных справа от данной. Сортировать элементы внутри групп нужно каким-то другим методом, и тут лучше всего подходит сортировка вставкой, поскольку массив уже почти упорядочен.

Т.о. для решения задачи сортировки целиком придется выполнить два вызова:
qsort4(0, n-1)
isort3()

Глубина рекурсии в среднем - (log (n-cutoff))
Производительность: ~ O(n*log n)
Расход памяти: ~ O(log (n-cutoff))