public class BucketSort
{
	public static void main( String args[] )
	{
		int arr[] = { 5,3,9,1,5,7,3,8,4,2,3,9,0,6,3,2,1,9,1,8,8,5,4,1 };
		bucketSort( arr, 9 );
		printArray( arr );
	}

	public static void printArray( int s[] )
	{
		for( int i = 0; i < s.length; i++ )
		{
			System.out.print( s[i] + " " );
		}
		System.out.println();
	}

	public static void bucketSort( int s[], int maxVal )
	{
		int m = maxVal+1;
		int[] buckets = new int[m];
		int n = s.length;

		for( int j = 0; j < m; j++ )
			buckets[j] = 0;

		for( int i = 0; i < n; i++ )
			buckets[s[i]]++;

		int i = 0;
		for( int j = 0; j < m; j++ )
			for( int r = 0; r < buckets[j]; r++ )
				s[i++] = j;
	}


}