Quick Sort

Quick Sort

void qSort(int s, int e) {
    if (s >= e) return;
    int l = s, r = e;
    auto pivot = data[(l+r)/2];

    while(l < r) {
        while(pivot < data[r]) --r;
        while(data[l] < pivot) ++l;
        if (l >= r) break;

        auto tmp = data[l];
        data[l] = data[r];
        data[r] = tmp;

        ++l, --r;
    }
    
    qSort(s, r);
    qSort(l, e);
}

Time Complexity

• Average: $O(N\log N)$
• Worst: $O(N^2)$