Быстрая сортировка с разделением

template<class T>
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.
 
  long i = 0, j = N;        // поставить указатели на исходные места
  T temp, p;
 
  p = a[ N>>1 ];        // центральный элемент
 
  // процедура разделения
  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
 
    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );
 
 
  // рекурсивные вызовы, если есть, что сортировать 
  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a+i, N-i);
}

#define MAXSTACK 2048       // максимальный размер стека
 
template<class T>
void qSortI(T a[], long size) {
 
  long i, j;            // указатели, участвующие в разделении
  
  long lb, ub;          // границы сортируемого в цикле фрагмента
 
  long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
                        // каждый запрос задается парой значений,
                        // а именно: левой(lbstack) и правой(ubstack) 
                        // границами промежутка
 
  long stackpos = 1;    // текущая позиция стека
  long ppos;            // середина массива
  T pivot;              // опорный элемент
  T temp; 
 
  lbstack[1] = 0;
  ubstack[1] = size-1;
 
  do {
 
    // Взять границы lb и ub текущего массива из стека.
 
    lb = lbstack[ stackpos ];
    ub = ubstack[ stackpos ];
    stackpos--;
 
    do {
      // Шаг 1. Разделение по элементу pivot
 
      ppos = ( lb + ub ) >> 1;
      i = lb; j = ub; pivot = a[ppos];
 
      do {
        while ( a[i] < pivot ) i++;
        while ( pivot < a[j] ) j--;
 
        if ( i <= j ) {
          temp = a[i]; a[i] = a[j]; a[j] = temp;
          i++; j--;
        }
      } while ( i <= j );
 
      // Сейчас указатель i указывает на начало правого подмассива,
      // j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
      // Возможен случай, когда указатель i или j выходит за границу массива
 
      // Шаги 2, 3. Отправляем большую часть в стек  и двигаем lb,ub
 
      if ( i < ppos ) {     // правая часть больше
 
        if ( i < ub ) {     //  если в ней больше 1 элемента - нужно 
          stackpos++;       //  сортировать, запрос в стек
          lbstack[ stackpos ] = i;
          ubstack[ stackpos ] = ub;
        }
        ub = j;             //  следующая итерация разделения
                            //  будет работать с левой частью
 
      } else {              // левая часть больше
 
        if ( j > lb ) { 
          stackpos++;
          lbstack[ stackpos ] = lb;
          ubstack[ stackpos ] = j;
        }
        lb = i;
      }
 
    } while ( lb < ub );        // пока в меньшей части более 1 элемента
 
  } while ( stackpos != 0 );    // пока есть запросы в стеке
}

#include <cstdlib>
#include <iostream>
#define MAXSTACK 2048
using namespace std;
 
 
using namespace std;
int *a = new int[10]; //выделяем память под массив из 10 элементов
 
void qSortI(int size) {
 
  int i, j;             // указатели, участвующие в разделении
  
  int lb, ub;       // границы сортируемого в цикле фрагмента
 
  int lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
                        // каждый запрос задается парой значений,
                        // а именно: левой(lbstack) и правой(ubstack) 
                        // границами промежутка
 
  int stackpos = 1;     // текущая позиция стека
  int ppos;            // середина массива
  int pivot;              // опорный элемент
  int temp; 
 
  lbstack[1] = 0;
  ubstack[1] = size-1;
 
  do {
 
    // Взять границы lb и ub текущего массива из стека.
 
    lb = lbstack[ stackpos ];
    ub = ubstack[ stackpos ];
    stackpos--;
 
    do {
      // Шаг 1. Разделение по элементу pivot
 
      ppos = ( lb + ub ) >> 1;
      i = lb; j = ub; pivot = a[ppos];
 
      do {
        while ( a[i] < pivot ) i++;
        while ( pivot < a[j] ) j--;
 
        if ( i <= j ) {
          temp = a[i]; a[i] = a[j]; a[j] = temp;
          i++; j--;
        }
      } while ( i <= j );
 
      // Сейчас указатель i указывает на начало правого подмассива,
      // j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
      // Возможен случай, когда указатель i или j выходит за границу массива
 
      // Шаги 2, 3. Отправляем большую часть в стек  и двигаем lb,ub
 
      if ( i < ppos ) {     // правая часть больше
 
        if ( i < ub ) {     //  если в ней больше 1 элемента - нужно 
          stackpos++;       //  сортировать, запрос в стек
          lbstack[ stackpos ] = i;
          ubstack[ stackpos ] = ub;
        }
        ub = j;             //  следующая итерация разделения
                            //  будет работать с левой частью
 
      } else {              // левая часть больше
 
        if ( j > lb ) { 
          stackpos++;
          lbstack[ stackpos ] = lb;
          ubstack[ stackpos ] = j;
        }
        lb = i;
      }
 
    } while ( lb < ub );        // пока в меньшей части более 1 элемента
 
  } while ( stackpos != 0 );    // пока есть запросы в стеке
}
 
int main()
{
    
    for (int i = 0; i < 10; i++)
    {
        a[i] = rand()%100;  //заполняем массив случайными числами
    }
    qSortI(10); //сортируем
    
    for (int i = 0; i < 10; i++)
    {
        cout << a[i] << endl;  //выводим отсортированный массив
    }
   return 0;
}