using System.Collections.Generic;

public interface RadixSortKey
{
    int DigitCount { get; } // Number of digits in key.
    int this[int i] { get; }  // Subscript 1 returns least 
    // significant digit.
    int Radix { get; }  // Returns the base for the radix 
    // representation.
}

public interface RadixSortElement<K>
      where K : struct, RadixSortKey
{
    K Key { get; }
}

public class RadixSorter<K, E>
    where K : struct, RadixSortKey
    where E : RadixSortElement<K>
{
    public static void sort(Queue<E> masterQ) {
            E rse = masterQ.Peek();
            Queue<E>[] subQ = new Queue<E>[rse.Key.Radix];
            for (int i=0; i<rse.Key.Radix; ++i) 
                subQ[i] = new Queue<E>();
            int binNumber, digitPosition = 1;
            E currentItem;
            while (digitPosition <= rse.Key.DigitCount) {
                while (masterQ.Count != 0) {
                    currentItem = masterQ.Peek();
                    masterQ.Dequeue();
                    binNumber = currentItem.Key[digitPosition];
                    subQ[binNumber].Enqueue(currentItem);
                }
                for (int k=0; k<rse.Key.Radix; ++k)
                    while (subQ[k].Count != 0)
                        masterQ.Enqueue(subQ[k].Dequeue())
                digitPosition++;
            }
        }
}
