Generic Quicksort implementation in C++

quicksort.cc

/* Ilya Pikulin, 2017
 * 
 * This is a generic implementation of quicksort.
 */

#include <algorithm>
#include <iostream>
#include <random>
#include <forward_list>
// #include <array>
// #include <vector>
// #include <list>

std::mt19937 mt((std::random_device()()));
std::uniform_int_distribution<size_t> dist;

// Quicksort. Pass a half-open interval
template<class It, class EndIt>
void quicksort(const It begin, 
               const EndIt end) {
  const auto distance = std::distance(begin, end);
  if (distance < 2) {
    return;
  } else if (distance == 2) {
    if (*begin > *std::next(begin)) {
      std::iter_swap(begin, std::next(begin));
    }
    return; 
  }

  std::iter_swap(begin, std::next(begin, dist(mt) % distance));

  auto x = begin;
  for (It it = std::next(x, 1); it != end; ++it) {
    if (*it < *begin) {
      std::iter_swap(++x, it);
    }
  }
  std::iter_swap(x, begin);

  auto y = x;
  for (It it = std::next(x, 1); it != end; ++it) {
    if (*it == *x) {
      std::iter_swap(++y, it);
    }
  }

  quicksort(begin, x);
  quicksort(std::next(y), end);
}

using value_type = uint16_t;
using Container = std::forward_list<value_type>;

int main() {
  Container v((std::istream_iterator<value_type>(std::cin)), std::istream_iterator<value_type>());
  quicksort(v.begin(), v.end());
  std::copy(v.begin(), v.end(), std::ostream_iterator<value_type>(std::cout, " "));
}