CareerCup

It can be done by performing Counting Sort twice.
For the first time the frequency of each number is counted in another array.
For the second time, we perform counting on the frequencies with same value.
Space complexity = O(4n). Time Complexity = O(5n). So basically both space and time complexities are of the order n.

#include <stdio.h>
# define ARY_SIZE 50
//a[] is input array, d[] is output array
int sortByFreq(int a[], int d[], int len) {  
    int b[len], c[len], i, newLen = 0;
    for(i = 0; i < len; i++) {
        b[i] = 0;
        c[i] = 0;
    }
// Frequency of each element is stored in b[]
    for(i = 0; i < len; i++) 
        b[a[i]]++;                       
// Counting for freq with same value in c[]
    for(i = 0; i < len; i++) 
        c[b[i]]++;                       
// indexing for the output in array d[]
    for(i = len - 2; i > 0; i--)
        c[i] += c[i+1];                  
// d[] is finally created now
    for(i = len - 1; i >= 0; i--) {    
        if(b[a[i]]) {
            d[c[b[a[i]]] - 1] = a[i];
            c[b[a[i]]]--;
            b[a[i]] = 0;
            newLen++;
        }
    }
    return newLen;
}

int main() {
    int len = 0, n;
    int a[ARY_SIZE];
    printf("Enter the numbers of the array:\n");
    while(scanf("%d", &n) == 1)
        a[len++] = n;
    int d[len];
    len = sortByFreq(a, d, len);
    printf("The sorted array in decreasing frequency is:\n");
    for(n = 0; n < len; n++)
        printf("%d  ", d[n]);
    printf("\n");
}

whether u want the result to be sorted by occur time or by the original order in the array?

It can be done with the concept of counting sort.

Pseudo code:- 
a= [3,4,2,5,3,3,4,2,1,5}
int n=a.length();
int B[]=new int[max(a)]; //initialise with zero
for i<- 0 to n-1
    do{
         B[a[i]]++;
         }
int start=0;
while(B!=null) // this whole loop will late o(m^2) time if m is large this method is not good
{ find max in B // in O(m) time m is the maximum element value
Let i th index is max
for(int j=start;j<B[i];j++)
{
          a[j]=i;
}

We can use the hashing and link list combination here.
First create a hash table and values will be the frequency of no.

eg: a= [3,4,2,5,3,3,4,2,1,5}

hash table of size 5 (biggest no)
let say it is h[5].
h[1] = 0, h[2]=2, h[3]=3, h[4]=2, h[5]=2.

Now iterate the hash table ans use insertion sort using linked list.

Use LinkedHashMap