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

namespace RadixSort
{
    class Program
    {
        List<int> unSortedList = new List<int>  {12,23,42,43,11,67,98,22,09,76,33,08,23,59,37,28,90,84,62,44,3,91,36,77,87,8,00,23};
        Queue<int>[] buckets=new Queue<int>[10];
        int modulo = 10;
        List<int> workSet = new List<int>();
        List<int> sortedList = new List<int>();
        int passesCompleted = 0;

        public void sort(){
            while (unSortedList.Count > 0){
                foreach (int ele in unSortedList){
                    bool elePlacedInBucket = false;
                    int bucket = ele % modulo;
                    while (!elePlacedInBucket){
                        if ((10 - bucket) > 0){
                            if(buckets[bucket] == null)
                                buckets[bucket]=new Queue<int>();
                            buckets[bucket].Enqueue(ele);
                            elePlacedInBucket = true;
                        }
                        else{
                            bucket = (bucket - (bucket % 10))/10;
                        }
                    }
                }

                foreach (Queue<int> q in buckets){
                    if (q != null){
                        while (q.Count > 0){
                            var ele = q.Dequeue();
                            if ((modulo - ele) > 0)
                                this.sortedList.Add(ele);
                            else
                                this.workSet.Add(ele);
                        }
                    }
                }

                modulo = modulo * 10;
                unSortedList = workSet.ConvertAll<int>((i)=>i);
                workSet.Clear();
                passesCompleted += 1;
            }
        }

        static void Main(string[] args)
        {
            Program p = new Program();
            p.sort();
            foreach (int ele in p.sortedList){
                Console.WriteLine(ele + " ");
            }
            Console.ReadKey();
        }
    }
}