Listing 2: Removing tail recursion to improve space efficiency in the presence of already-sorted data

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 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);
    sort(--first1, last1, depth + 1);
    first = first2;
    last = last2;
    }
}
— End of Listing —