The Full Counting Sort

                            Solution in C :

In  C++  :







#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<string>
#include<list>
using namespace std;


vector<string> a[100];
char str[100007];
int n,i,j,x;

int main() {
   
    
    
    cin>>n;
    for(i=0;i<n/2;i++)
    {
        cin>>x;
        cin>>str;
        a[x].push_back("-");
    
    }
    
    for(;i<n;i++)
    {
        cin>>x;
        cin>>str;
        a[x].push_back(str);
    
    }
    
    for(i=0;i<100;i++)
    {
        x=a[i].size();
        for(j=0;j<x;j++)
            cout<<a[i][j]<<" ";    
    }
    return 0;

}










In   Java  :






import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        StringBuffer[] map = new StringBuffer[100];
        for(int i = 0; i < 100; i++) {
            map[i] = new StringBuffer();
        }
        for(int i = 0; i < n; i++) {
            StringTokenizer tok = new StringTokenizer(in.readLine());
            int v = Integer.parseInt(tok.nextToken());
            String s = tok.nextToken();
            map[v].append(i < n / 2 ? "-" : s).append(" ");
        }
        for(int i = 0; i < 100; i++) {
            System.out.print(map[i]);
        }
        System.out.println();
    }
}










In   C  :








#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int* hist[100];
int size[100];
int pos[100];

int main() {
    int BUF_SZ = 256;
    int N, v, i, j;
    scanf("%d", &N);
    fprintf(stderr, "%d elements\n", N);
    char *data[N];
    for (i = 0; i < N; ++i) {
        if (i < N/2) {
            data[i] = (char*)malloc(BUF_SZ*sizeof(char));
        }
        scanf("%d %s", &v, data[i<N/2?i:i-N/2]);
        if (hist[v] == NULL) {
            size[v] = 2*N/100 + 1;
            hist[v] = (int*)malloc(size[v]*sizeof(int));
        } else if (pos[v] >= size[v]) {
            size[v] *= 2;
            hist[v] = (int*)realloc(hist[v], size[v]*sizeof(int));
        }
        (hist[v])[pos[v]++] = i;
    }
    for (i = 0; i < 100; ++i) {
        fprintf(stderr, "Printing %d\n", i);
        for (j = 0; j < pos[i]; ++j) {
            if ((hist[i])[j] < N/2) {
                printf("- ");
            } else {
                printf("%s ", data[(hist[i])[j]-N/2]);
                free(data[(hist[i])[j]-N/2]);
            }
        }
        if (hist[i] != NULL) {
            free(hist[i]);
            hist[i] = NULL;
        }
    }
    return 0;
}










In   Python3  :






n = int(input())
ar = []
for i in range(0,n) :
    data = input().strip().split(' ')
    ar.append((int(data[0]), data[1]))

c = [0]*100
for a in ar :
    c[a[0]] += 1
    
c1 = [0]*100
for x in range(1,100) :
    c1[x] = c1[x-1] + c[x-1]

s = ['-']*n
for i in range(0,n) :
    if i >= n/2 :
        s[c1[ar[i][0]]] = ar[i][1]
    c1[ar[i][0]] += 1
    
print(' '.join(s))