template<class T>
void QSort3(T* x, int l, int u) {
    if (l >= u)
        return;
 
    T t, tmp;
    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):
        tmp = x[i]; x[i] = x[j]; x[j] = tmp;
    }
 
    // swap(l, j)
    tmp = x[l]; x[l] = x[j]; x[j] = tmp;
 
    QSort3(x, l, j-1);
    QSort3(x, j+1, u);
}

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

Это хорошо подходит для случайных входных данных, но может сильно замедлить работу для некоторых упорядоченных последовательностей. Если массив уже отсортирован по возрастанию, его придется разбивать относительно первого элемента, затем относительно второго и так далее, что потребует времени О(n²).

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