gistfile1.cpp

namespace detail {

template <class IterT>
IterT partition(IterT begin, IterT end) {

    // The pivot is the first element of this array section
    IterT pivotIdx = begin;
    auto pivot = *(begin++);

    while(begin < end){
        while (*begin < pivot) begin++;
        while (*(end-1) > pivot) end--;

	if (begin >= end) break;

	std::swap(*begin, *(end-1));
	++begin; --end;
    }
   
    // insert the pivot element in the correct position
    std::swap(*pivotIdx, *(end-1));
    return end-1;
}

} // end detail namespace 

template <class IterT>
void quicksort(const IterT& begin, const IterT& end) {
    if (begin < end) {
        // Return the index of the new partition 
        auto newPivot = detail::partition(begin, end);
        // Recur on the two halves 
        quicksort(begin, newPivot);
        quicksort(newPivot+1, end);
    }
}