#include <iostream>

using namespace std;

/** Quick Sort
 *
 * split: cmp && swap
 * left
 * right
 *
 */
template <typename T>
int split(T* a, int low, int high) {
while(low < high) {
        while(a[low] <= a[high] && low < high){
            low ++;
        }
        swap(a[low], a[high]); /// swap
        while (a[low] <= a[high] && low < high){
            high --;
        }
        swap(a[low], a[high]); ///swap
    }
    return low;
}

template <typename T>
void quickSort(T* a, int low, int high) {
    if(low < high) {
        int key = split(a, low, high);
        cout << "key:" << key <<endl;
        quickSort(a,low, key-1);
        quickSort(a,key+1, high);
    }
}