quicksort with bidirectional iterators

quicksort.cpp

// Iterators need only be bidirectional, no random access needed
template <typename Iterator> void quicksort(const Iterator begin, const Iterator end)
{
    // empty sequence
    if (begin == end) {
	    return;
    }

    auto right = end;
    right--;

    // sequence with single element
    if (begin == right) {
	    return;
    }

    auto left = begin;
    while (left != right) {
	    if (*left <= *begin) {
		    left++;
	    } else if (*right > *begin) {
		    right--;
	    } else {
		    iter_swap(left, right);
	    }
    }

    // put pivot in place
    if (*left > *begin) {
        left--;
    }
    iter_swap(begin, left);

    // sort subvectors
    quicksort(begin, left);
    quicksort(right, end);
}