Listing 1: A first-cut implementation of quicksort

#include <algorithm>
#include <iostream>
#include <iterator>

class item
{
public:
    item() : val(0) {}
    explicit item(int v) : val(v) {}
    item(const item& other) : val(other.val) {}
    item& operator = (const item& other)
        { val = other.val; return *this; }
    friend std::ostream& operator <<
        (std::ostream& os, const item& it)
        { return os << it.val; }
    bool operator < (const item& other) const
        { return val < other.val; }
private:
    int val;
};

static int maxdepth = 0;
static int ops = 0;

template<class RanIt>
void sort(RanIt first, RanIt last, int depth = 0)
{
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);
sort(first2, last2, depth + 1);
}

const int ELTS = 100000;
item data[ELTS];

int main()
    {
    for (int i = 0; i < ELTS; ++i)
        data[i] = item(i);
    std::random_shuffle(data, data + ELTS);    
    sort(data, data + ELTS);
    std::cout << "max depth: " << maxdepth << '\n';
    std::cout << "operations: " << ops << '\n';
    return 0;
    }
— End of Listing —