Count Sort

Intuition

This works as follow,

• you are given array arr with numbers within range \([1, n]\)
• first you find the relative frequency of all numbers form \([1, n]\) in arr
• then you calculate the cumulative frequency
• now position of a particular element \(x\) in the sorted array will be the cumulative frequency of the \(x-1\) because that many elements will appear before it in the array.

#include <bits/stdc++.h>
using namespace std;

#define N 10

void count_sort(vector<int> &a) {
    vector<int> c(N, 0);
    vector<int> out(a.size(), 0);
    for (auto i : a) c[i]++;                             // relative freq
    for (int i = 1; i < c.size(); i++) c[i] += c[i - 1]; // cumulative freq
    // for (int i = 0; i < a.size(); i++) out[c[a[i] - 1]++] = a[i]; // unstable
    for (int i = a.size() - 1; i >= 0; i--) out[c[a[i]]-- - 1] = a[i]; // stable
    a = out;
}

int main() {
    vector<int> a = {1, 4, 0, 2, 5, 5, 6, 3, 3, 4};
    count_sort(a);
    for (auto i : a) cout << i << " ";
    return 0;
}

Analysis

• \(k\) - the range of numbers
• \(n\) - the size of array
• Time complexity
  • Best: \(O(n+k)\), if the array is sorted
  • Average: \(O(n+k)\)
  • Worst: \(O(n+k)\)
• Space complexity - \(O(k+n)\)