Bucket Sort

Bucket sort is mainly useful when input is uniformly distributed over a range.

Void Bucket_Sort(int X[n], int n)
    {
    int i,j, Y[n+1];
    for (i = 0; i < n; i++) Y[i] = 0;
    for (i = 0; i < n; i++) Y[X[i]]++;
    for (i = 0, j = 0; i < n; i++)
        while(Y[i]-- > 0) X[j++] = i
    }

Runtime – O(n)