Counting Sort

CountingSort.hpp

#include <algorithm>
#include <numeric>

template <typename InputIter, typename OutputIter, typename BucketIter,
          typename KeyFunction>
void counting_sort(InputIter First, InputIter Last, BucketIter BucketFirst,
                   BucketIter BucketLast, OutputIter OutputFirst,
                   KeyFunction Key) {
  std::fill(BucketFirst, BucketLast, 0);
  for (auto Iter = First; Iter != Last; ++Iter)
    ++(*(BucketFirst + Key(*Iter)));
  std::partial_sum(BucketFirst, BucketLast, BucketFirst);
  do {
    --Last;
    *(OutputFirst + --(*(BucketFirst + Key(*Last)))) = std::move(*Last);
  } while (Last != First);
}

main.cpp

#include "CountingSort.hpp"
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
using namespace std;

int main() {
  vector<pair<int, int>> V1;
  mt19937 MT(7122);
  const int N = 10000000, A = 1000, B = 10000;
  for (int i = 0; i < N; ++i) {
    V1.emplace_back(MT() % A, MT() % B);
  }
  decltype(V1) V2 = V1;

  auto Begin = chrono::high_resolution_clock::now();
  sort(V2.begin(), V2.end());
  auto End = chrono::high_resolution_clock::now();
  cout << "std::sort: "
       << chrono::duration_cast<chrono::milliseconds>(End - Begin).count()
       << "ms\n";

  Begin = chrono::high_resolution_clock::now();
  decltype(V2) Tmp(V1.size());
  vector<int> Bucket(max(A, B), 0);
  counting_sort(V1.begin(), V1.end(), Bucket.begin(), Bucket.begin() + B,
                Tmp.begin(), [&](const auto &P) -> int { return P.second; });
  counting_sort(Tmp.begin(), Tmp.end(), Bucket.begin(), Bucket.begin() + A,
                V1.begin(), [&](const auto &P) -> int { return P.first; });
  End = chrono::high_resolution_clock::now();
  cout << "radix_sort: "
       << chrono::duration_cast<chrono::milliseconds>(End - Begin).count()
       << "ms\n";

  assert(V1 == V2);
  return 0;
}