C++ implementation of quicksort with iterators (unstable sorting) Please review the following quicksort implementation.
qsort below is intentionally unstable, as partition reoders equal elements.

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

using namespace std;

// Ensures pivot is at position end.
template&lt;typename Iter, typename T&gt;
Iter part_pivot(Iter begin, Iter end, T pivot) {
  while (begin != end) {
    if (*begin &lt; pivot)
      ++begin;
    else if (*--end &lt; pivot)
      iter_swap(begin, end);
  }
  return begin;
}

template&lt;typename Iter&gt;
Iter part(Iter begin, Iter end) {
  typename iterator_traits&lt;Iter&gt;::value_type pivot = *begin;
  Iter mid = part_pivot(begin, end, pivot);
  // Ensure pivot is at position mid.
  iter_swap(--end, mid);
  return mid;
}

template&lt;class Iter&gt;
void quicksort(Iter begin, Iter end) {
  if (std::distance(begin, end) &lt; 2)
    return;
  Iter mid = part(begin, end, *begin);
  quicksort(begin, mid);
  quicksort(++mid, end);
}

template&lt;class T&gt;
void quicksort(vector&lt;T&gt;&amp; v) {
  quicksort(v.begin(), v.end());
}

template &lt;class T&gt;
void print(const vector&lt;T&gt;&amp; v) {
  for (const T&amp; t : v)
    cout &lt;&lt; t &lt;&lt; " ";
  cout &lt;&lt; endl;
}

int main() {
  vector&lt;int&gt; v = {1,4,8,34,2,3,45,6,87,4,3};
  print(v);
  quicksort(v);
  print(v);
}
Two problems with the code that I see immediately:


if (std::distance(begin, end) &lt;= 2) is wrong since it leaves an array like {2,1} untouched. This means that the code can screw up every time it recurses to an array of size 2.
Iter partition(Iter begin, Iter end, const T&amp; pivot): Passing pivot as const T&amp; is a bad idea. When passed as const reference, when you perform the iter_swap, the value pointed to by begin changes and so does pivot. Hence running your code gives me a segfault but changing const T&amp; to T takes care of the segfault.


Even if these are fixed, there is something more subtle. Suppose you try to sort an already sorted array like {1,1,1}. Partitioning this will return mid = begin. So unless you make an explicit check for a sorted array you will recurse infinitely on qsort(mid,end).