void quicksort(a: T[n], int l, int r)
     T v = a[r]
     if (r <= l)
        return
     int i = l
     int j = r - 1
     int p = l - 1
     int q = r
     while true
        while (a[i++] < v)
        while (a[j--] > v)
        if (i == j)
           break
        if (i >= j)
           break
        swap(a[i], a[j])
        if (a[i] == v)
           p++
           swap(a[p], a[i])
        if (a[j] == v)
           q--
           swap(a[q], a[j])
     swap(a[i], a[r])
     j = i - 1
     i++
     for (int k = 1; k <= p; k++, j--)
        swap(a[k], a[j])
     for (int k = r - 1; k >= q; k--, i++)
        swap(a[k], a[i])
     quicksort(a, 1, j)
     quicksort(a, i, r)

void quicksort(int a[], int l, int r) {
        int v = a[r];
        if (r <= l)
            return;
        int i = l;
        int j = r-1;
        int p = l-1;
        int q = r;

        while(true) {
            while (a[i++] < v);
            while (a[j--] > v);
                    if (i >= j) {
                        break;
                    }
                    exch(a, i, j);
                    if (a[i] == v) {
                        p++;
                        exch(a, p, i);
                    }
                    if (a[j] == v) {
                        q--;
                        exch(a, q, j);
                    }
                    exch(a, i, r);
                    j = i - 1;
                    i++;
                    for (int k = 1; k <= p; k++, j--) {
                        exch(a, k, j);
                    }
                    for (int k = r - 1; k >= q; k--, i++) {
                        exch(a, k, i);
                    }
                    quicksort(a, 1, j);
                    quicksort(a, i, r);
        }
    }

    void exch(int[] a, int i, int j){
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }