QuickSort Survey

template<Util::Array C>
auto pivot(C& v, typename C::size_type start,  typename C::size_type stop, typename C::size_type position) -> typename C::size_type {
    using std::swap;
    swap(v[start], v[position]);

    typename C::size_type low = start + 1;
    typename C::size_type high = stop;
    while (low < high)
        if (v[low] < v[start])
            ++low;
        else if (v[--high] < v[start])
            swap (v[low], v[high]);

    swap (v[start], v[--low]);
    return low;
}
template<Util::Array C>
void quickSort(C& v, typename C::size_type low, typename C::size_type high) {
    if (low >= high)
        return;

    typename C::size_type pivotIndex = (low + high) / 2;

    pivotIndex = pivot (v, low, high, pivotIndex);

    if (low < pivotIndex)
        quickSort(v, low, pivotIndex);
    if (pivotIndex < high)
        quickSort(v, pivotIndex + 1, high);
}

template<Util::Array C>
void quickSort(C& a, typename C::signed_size_type l, typename C::signed_size_type r) {
    using std::swap;
    typename C::signed_size_type i = l-1, j = r, p = l-1, q = r;
    if (r <= l) return;
    auto v = a[r];
    while(true) {
        while (a[++i] < v) ;
        while (v < a[--j]) if (j == l) break;
        if (i >= j) break;
        swap(a[i], a[j]);
        if (a[i] == v) {
            ++p;
            swap(a[p], a[i]);
        }
        if (v == a[j]) {
            --q;
            swap(a[j], a[q]);
        }
    }
    swap(a[i], a[r]);
    j = i-1;
    i = i+1;
    for (auto k = l; k < p; k++, j--) swap(a[k], a[j]);
    for (auto k = r-1; k > q; k--, i++) swap(a[i], a[k]);
    quickSort(a, l, j);
    quickSort(a, i, r);
}

// ...
template<typename T>
T* med3(T* a, T* b, T* c) {
    return (*a < *b) ?
           ((*b < *c) ? b : ((*a < *c) ? c : a ))
           :((*b > *c) ? b : ((*a < *c) ? a : c ));
}
template<typename T, typename SizeType>
void qsort(T* a, SizeType n) {
    using std::swap;

    T *pa, *pb, *pc, *pd, *pl, *pm, *pn;
    SizeType d, r, swap_cnt;
loop:
    swap_cnt = 0;
    if (n < 7) {
        for (pm = a + 1; pm < (a + n); ++pm)
            for (pl = pm; pl > a && (*(pl - 1) > *pl);
                    --pl)
                swap(*pl, *(pl - 1));
        return;
    }
    pm = a + (n / 2);
    if (n > 7) {
        pl = a;
        pn = a + (n - 1);
        if (n > 40) {
            d = (n / 8);
            pl = med3(pl, pl + d, pl + 2 * d);
            pm = med3(pm - d, pm, pm + d);
            pn = med3(pn - 2 * d, pn - d, pn);
        }
        pm = med3(pl, pm, pn);
    }
    swap(*a, *pm);
    pa = pb = a + 1;

    pc = pd = a + (n - 1);
    for (;;) {
        while ((pb <= pc) && (*pb <= *a)) {
            if (*pb == *a) {
                swap_cnt = 1;
                swap(*pa, *pb);
                pa += 1;
            }
            pb += 1;
        }
        while (pb <= pc && (*pc >= *a)) {
            if (*pc == *a) {
                swap_cnt = 1;
                swap(*pc, *pd);
                pd -= 1;
            }
            pc -= 1;
        }
        if (pb > pc)
            break;
        swap(*pb, *pc);
        swap_cnt = 1;
        pb += 1;
        pc -= 1;
    }
    if (swap_cnt == 0) {  /* Switch to insertion sort */
        for (pm = a + 1; pm < a + n; ++pm)
            for (pl = pm; pl > a && (*(pl - 1) > *pl);
                    --pl)
                swap(*pl, *(pl - 1));
        return;
    }

    pn = a + n;
    r = std::min(pa - a, pb - pa);
    vecswap(a, pb - r, r);
    r = std::min(pd - pc, pn - pd - 1);
    vecswap(pb, pn - r, r);
    if ((r = pb - pa) > 1)
        qsort(a, r);
    if ((r = pd - pc) > 1) {
        a = pn - r;
        n = r;
        goto loop;
    }
}