While browsing Wikipedia I came across the wiki entry for computational sorting methods and one thing on the page struck me as odd. They had a whole list of non-comparison sorting methods that sort things without ever checking them against the other items in the list (hence the name ) so I thought I’d see if I could come up with a quick Radix sort and see if I can get linear performance out of it (Which the Wikipedia article says its capable of).

This is what I came up with 114 lines not tweaked too much. And yes this code provides a linear search time (e.g. the number of items doubles so does the time needed to sort). On my machine I tested it from 10,000 to 5,120,000 items (by doubling the ammount of items each time 10 test with 4 runs each test to average the time) and it took on average 0.008954888 milliseconds per item regardless of how many there were.

So here’s the code in C#/mono. There’s probably a million ways to optimize it put I was just interested in see how the Radix sort worked in general I might try to make it faster in the future but this is it for now.

NOTE: this program is meant to be run from the command line with the following syntax -> c:\PATH-TO-PROGRAM\Program.exe

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
namespace RadixSort
{
    class Program
    {
        static void Main(string[] args)
        {
            System.Random rand = new Random(System.DateTime.Now.Millisecond);
            int items = Convert.ToInt32(args[0]);
            ArrayList Items = new ArrayList();
            int c = 0;
            while (c <= items)
            {
                Items.Add(rand.Next(0,999));
                c++;
            }
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            ArrayList sorted = RadixSort(Items,3);
            sw.Stop();
            Console.WriteLine("Sorted in :: "+sw.Elapsed.Seconds.ToString() +
            " Seconds and "+sw.Elapsed.Milliseconds.ToString()+" milliseconds");
        }
        static ArrayList RadixSort (ArrayList Items, int Digits)
        {
            ArrayList RetValue = new ArrayList();
            RetValue = Items;
            int Digit = Digits - 1;
            while (Digit >= 0)
            {
                ArrayList Zero = new ArrayList();
                ArrayList One = new ArrayList();
                ArrayList Two = new ArrayList();
                ArrayList Three = new ArrayList();
                ArrayList Four = new ArrayList();
                ArrayList Five = new ArrayList();
                ArrayList Six = new ArrayList();
                ArrayList Seven = new ArrayList();
                ArrayList Eight = new ArrayList();
                ArrayList Nine = new ArrayList();
                foreach (int i in RetValue)
                {
                    if (i.ToString().PadLeft(Digits,'0')[Digit] == '0')
                    {
                        Zero.Add(i);
                        continue;
                    }
                    if (i.ToString().PadLeft(Digits,'0')[Digit] == '1')
                    {
                        One.Add(i);
                        continue;
                    }
                    if (i.ToString().PadLeft(Digits,'0')[Digit] == '2')
                    {
                        Two.Add(i);
                        continue;
                    }
                    if (i.ToString().PadLeft(Digits,'0')[Digit] == '3')
                    {
                        Three.Add(i);
                        continue;
                    }
                    if (i.ToString().PadLeft(Digits,'0')[Digit] == '4')
                    {
                        Four.Add(i);
                        continue;
                    }
                    if (i.ToString().PadLeft(Digits,'0')[Digit] == '5')
                    {
                        Five.Add(i);
                        continue;
                    }
                    if (i.ToString().PadLeft(Digits,'0')[Digit] == '6')
                    {
                        Six.Add(i);
                        continue;
                    }
                    if (i.ToString().PadLeft(Digits,'0')[Digit] == '7')
                    {
                        Seven.Add(i);
                        continue;
                    }
                    if (i.ToString().PadLeft(Digits,'0')[Digit] == '8')
                    {
                        Eight.Add(i);
                        continue;
                    }
                    if (i.ToString().PadLeft(Digits,'0')[Digit] == '9')
                    {
                        Nine.Add(i);
                        continue;
                    }
                }
                RetValue = new ArrayList();
                foreach (int i in Zero)
                {
                    RetValue.Add(i);
                }
                foreach (int i in One)
                {
                    RetValue.Add(i);
                }
                foreach (int i in Two)
                {
                    RetValue.Add(i);
                }
                foreach (int i in Three)
                {
                    RetValue.Add(i);
                }
                foreach (int i in Four)
                {
                    RetValue.Add(i);
                }
                foreach (int i in Five)
                {
                    RetValue.Add(i);
                }
                foreach (int i in Six)
                {
                    RetValue.Add(i);
                }
                foreach (int i in Seven)
                {
                    RetValue.Add(i);
                }
                foreach (int i in Eight)
                {
                    RetValue.Add(i);
                }
                foreach (int i in Nine)
                {
                    RetValue.Add(i);
                }
                Digit--;
            }
            return RetValue;
        }
    }
}