### RK Sorting

*given below code is for rks spoj or rk sorting spoj*

#include <iostream> #include <stdio.h> using namespace std; struct data { long num; int count; int check; int appear; public: data() { num=0; count=0; check=1; appear=0; } }; #define Data struct data void mergesort(Data D[],int low,int mid,int high,int n) { int i=low,j=mid+1,k=low; Data temp[n]; while(i<=mid && j<=high) { if(D[i].count>D[j].count) temp[k++]=D[i++]; else if(D[i].count==D[j].count) { temp[k++]= D[i].appear < D[j].appear ? D[i++] : D[j++]; } else temp[k++]=D[j++]; } while(i<=mid) temp[k++]=D[i++]; while(j<=high) temp[k++]=D[j++]; for(int l=low;l<=high;l++) D[l]=temp[l]; } void partition(Data D[],int low,int high,int n) { int mid; if(low<high) { mid=(low+high)/2; partition(D,low,mid,n); partition(D,mid+1,high,n); mergesort(D,low,mid,high,n); } } int main() { int n; long c,temp; scanf("%d%ld",&n,&c); Data D[n+1]; for(int i=0;i<n;i++) { scanf("%d",&D[i].num); } int m=0; for(int i=0;i<n;i++) { if(D[i].check==1){ for(int j=0;j<n;j++) { if(D[i].num == D[j].num) { D[i].appear=m; D[i].count++; D[j].check=0; } } m++; } } partition(D,0,n-1,n); for(int i=0;i<n;i++){ for(int j=0;j<D[i].count;j++) printf("%d ",D[i].num); } return 0; }