#include "iostream.h"
#include "stdio.h"

void quickSort( int *array, int L, int R ){
int i, j;
int item, temp;
	i = L;
	j = R;
	item = array[(L + R)/2];
	while ( i <= j ){
		while ( array[i] < item ) i++;
		while ( item < array[j] ) j--;
		if ( i <= j ){ 
			temp = array[i];
			array[i] = array[j];
			array[j] = temp;
			i++;
			j--;
		}
	}
	if ( L < j ) quickSort( array, L, j );
	if ( i < R ) quickSort( array, i, R );
}

void main(){
	int i, size;
	int *array;
    cout << "Quick Sort.\nEnter array dimension: ";
    cin >> size;
	array = new int[size];
    cout << "Enter " << size << " elements: ";
	for ( i = 0; i < size; i ++ ){
		cin >> array[i];
	}

	quickSort( array, 0, size - 1 );

	cout << "Your array after sorting: ";
	for ( i = 0; i < size; i ++ ){
		cout << array[i] << " ";
	} 
    cout << "\nPress \"Enter\" to continue..." << endl; 
    getchar();
}

template<class T>
void merge(T a[], long lb, long split, long ub) {
// Слияние упорядоченных частей массива в буфер temp
// с дальнейшим переносом содержимого temp в a[lb]...a[ub]

  // текущая позиция чтения из первой последовательности a[lb]...a[split]
  long pos1=lb;

  // текущая позиция чтения из второй последовательности a[split+1]...a[ub]
  long pos2=split+1;

  // текущая позиция записи в temp
  long pos3=0;  

  T *temp = new T[ub-lb+1];

  // идет слияние, пока есть хоть один элемент в каждой последовательности
  while (pos1 <= split && pos2 <= ub) {
    if (a[pos1] < a[pos2])
      temp[pos3++] = a[pos1++];
    else
      temp[pos3++] = a[pos2++];
  }

  // одна последовательность закончилась - 
  // копировать остаток другой в конец буфера 
  while (pos2 <= ub)   // пока вторая последовательность непуста 
    temp[pos3++] = a[pos2++];
  while (pos1 <= split)  // пока первая последовательность непуста
    temp[pos3++] = a[pos1++];

  // скопировать буфер temp в a[lb]...a[ub]
  for (pos3 = 0; pos3 < ub-lb+1; pos3++)
    a[lb+pos3] = temp[pos3];

  delete temp[ub-lb+1];
}