C++ implementation of quicksort with iterators (unstable sorting)

Question

Please review the following quicksort implementation. qsort below is intentionally unstable, as partition reoders equal elements.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

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

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

template<class T>
void quicksort(vector<T>& v) {
  quicksort(v.begin(), v.end());
}

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

int main() {
  vector<int> v = {1,4,8,34,2,3,45,6,87,4,3};
  print(v);
  quicksort(v);
  print(v);
}

Answer 1

Two problems with the code that I see immediately:

1. if (std::distance(begin, end) <= 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.

2. Iter partition(Iter begin, Iter end, const T& pivot): Passing pivot as const T& 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& 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).