int partition(vector<int>& v, int piv, int low, int high) {
    int i = low-1;
    int j = high+1;
    while (low <= high) {
        do { i++; } while(v[i] < piv);
        do { j--; } while(v[j] > piv);
        if (i >= j) return j;
        swap(v[i], v[j]);
    }
}

int pivot(vector<int>& v, int l, int h) {
    int a = v[l];
    int b = v[(l+h)/2];
    int c = v[h];
    if ((a <= b && b <= c) || (a >= b && b >= c)) return b;
    else if ((a <= c && c <= b) || (a >= c && c >= b)) return c;
    else return a;
}

void insertionsort(vector<int>& v) {
    for (int i = 1; i < v.size(); ++i) {
        int j = i;
        while (j > 0 && v[j-1] > v[j]) {
            swap(v[j-1], v[j]);
            j--;
        }
    }
}

void quicksort(vector<int>& v, int low, int high) {
    if (low < high) {
        if (v.size() < 150) {
            insertionsort(v);
            return;
        }
        int piv = pivot(v, low, high);
        int p = partition(v, piv, low, high);
        quicksort(v, low, p);
        quicksort(v, p+1, high);
    }
}

int main() {
    vector<int> v;
    // bool b = true;
    // while (b) {
    //     int n;
    //     cin >> n;
    //     if (n == 0) break;
    //     v.push_back(n);
    // }
    srand(time(0));
    for (int i = 0; i < 100000; ++i) {
        int x = rand();
        v.push_back(x);
    }
    // for (int i : v) cout << i << " ";
    // cout << "\n";
    auto start = high_resolution_clock::now();
    quicksort(v, 0, v.size()-1);
    auto stop = high_resolution_clock::now();
    // for (int i : v) cout << i << " ";
    // cout << "\n";
    auto duration = duration_cast<microseconds>(stop-start);
    cout << "time: " << duration.count() << "\n";
}