#include <iostream>
#include <iomanip>
 
using namespace std;
 
template<typename T>
void quickSort1(T* array, long N)
{
    long i = 0, j = N - 1;
    T p = array[N >> 1];
 
    do {
        while (array[i] > p) i++;
        while (array[j] < p) j--;
 
        if (i <= j) {
            T temp = array[i]; array[i] = array[j]; array[j] = temp;
            i++; j--;
        }
    } while (i <= j);
 
    if (j > 0) quickSort1(array, j+1);
    if (N > i) quickSort1(array + i, N - i);
}
 
int main(int argc, char * argv[])
{
    int a[40];
    for(int i = 0; i < 40; ++i) a[i] = rand()%100;
    for(int i: a) cout << i << " "; cout << "\n";
    quickSort1(a,40);
    for(int i: a) cout << i << " "; cout << "\n";
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBUPgp2b2lkIHF1aWNrU29ydDEoVCogYXJyYXksIGxvbmcgTikKewogICAgbG9uZyBpID0gMCwgaiA9IE4gLSAxOwogICAgVCBwID0gYXJyYXlbTiA+PiAxXTsKCiAgICBkbyB7CiAgICAgICAgd2hpbGUgKGFycmF5W2ldID4gcCkgaSsrOwogICAgICAgIHdoaWxlIChhcnJheVtqXSA8IHApIGotLTsKCiAgICAgICAgaWYgKGkgPD0gaikgewogICAgICAgICAgICBUIHRlbXAgPSBhcnJheVtpXTsgYXJyYXlbaV0gPSBhcnJheVtqXTsgYXJyYXlbal0gPSB0ZW1wOwogICAgICAgICAgICBpKys7IGotLTsKICAgICAgICB9CiAgICB9IHdoaWxlIChpIDw9IGopOwoKICAgIGlmIChqID4gMCkgcXVpY2tTb3J0MShhcnJheSwgaisxKTsKICAgIGlmIChOID4gaSkgcXVpY2tTb3J0MShhcnJheSArIGksIE4gLSBpKTsKfQoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgKiBhcmd2W10pCnsKICAgIGludCBhWzQwXTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCA0MDsgKytpKSBhW2ldID0gcmFuZCgpJTEwMDsKICAgIGZvcihpbnQgaTogYSkgY291dCA8PCBpIDw8ICIgIjsgY291dCA8PCAiXG4iOwogICAgcXVpY2tTb3J0MShhLDQwKTsKICAgIGZvcihpbnQgaTogYSkgY291dCA8PCBpIDw8ICIgIjsgY291dCA8PCAiXG4iOwp9Cg==