using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BucketSort
{
    class Program
    {
        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);
            Console.ReadLine();
        }

        static void PrintArray(int[] s)
        {
            for (int i = 0; i < s.Length; i++)
            {
                Console.Write("{0} ", s[i]);
            }
            Console.WriteLine();
        }

        static void BucketSort(int[] s, int maxVal)
        {
            int i, j;
            int m = maxVal + 1;
            int[] buckets = new int[m];
            int n = s.Length;

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

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

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