sort_Counting.cpp

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

void countSort(vector<int>&array, int size)
 {
  int max = array[0];
  for (int i = 1; i < size; i++)
   {
    if (array[i] > max)  max = array[i];
   }
    vector<int>output(size,0);
    vector<int>count(max+10,0);

  for (int i = 0; i < size; i++) count[array[i]]++;
  for (int i = 1; i <= max; i++) count[i] += count[i - 1];
  
  // Find the index of each element of the original array in count array, and
  // place the elements in output array
  for (int i = size - 1; i >= 0; i--) {
    output[--count[array[i]] ] = array[i];
 //   count[array[i]]--;
  }

  for (int i = 0; i < size; i++)  array[i] = output[i];
} 



int main() {

  int n;
  cin>>n;
  vector<int>array(n);
  for(int i=0;i<n;i++) cin>>array[i];
  countSort(array, n);
  for (int i = 0; i < n; i++) cout << array[i] << " ";

}