Listing 4: Using the "median of three" approach for selecting pivots to improve time efficiency

template<class RanIt>
void sort(RanIt first, RanIt last, int depth = 0)
{
for (;;)
    {
    if (last - first <= 1)
        return;
    ops += last - first;
    if (maxdepth < depth)
        maxdepth = depth;

    RanIt mid = first + (last - first) / 2;
    if (*first < *mid)
        std::iter_swap(first, mid);
    if (*(last - 1) < *first)
        std::iter_swap(last - 1, first);
    if (*first < *mid)
        std::iter_swap(first, mid);

    RanIt pivot = first;
    RanIt first1, last1;
    RanIt first2, last2;
    first1 = last1 = first + 1;
    first2 = last2 = last;

    for (;;)
        {
        while (last1 < first2 && *last1 < *pivot)
            ++last1;
        while (last1 <= first2 - 1 && *pivot < *(first2 - 1))
            --first2;
        if (first2 <= last1)
            break;
        std::iter_swap(last1++, --first2);    
        }

    std::iter_swap(pivot, --last1);
    --first1;
    if (last1 - first1 < last2 - first2)
        {
        sort(first1, last1, depth + 1);
        first = first2;
        last = last2;
        }
    else
        {
        sort(first2, last2, depth + 1);
        first = first1;
        last = last1;
        }
    }
}
— End of Listing —