C#で実装したradix sortとArray.Sortのquick sortとの比較

radix sort（基数ソート）のコードを書いてて、適当に処理速度を比較してみたら遅かったから簡単なベンチマークを書いてみた。
比較するのは次の3つ。

• radix sort（WikipediaのRadix sortとstereopsisのradix tricksを参考にして書いたコード）
• comb sort（WikipediaのComb sortを参考に書いたコード、というかほぼそのまま）
• quick sort（.NET Framework 3.5のArray.Sort）

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

namespace SortBenchmark
{
    class Program
    {
        static void Main(string[] args)
        {
            for (var size = 1000; size <= 1000000; size *= 10)
                Run(size);
        }

        static void Run(int size)
        {
            Console.WriteLine("size: {0}", size);

            var count = 10;
            var sw = new Stopwatch();
            var radixSortTicks = 0L;
            var combSortTicks = 0L;
            var arraySortTicks = 0L;
            for (var c = 0; c < count; c++)
            {
                var random = new Random(c);
                var list = new UInt32[size];
                for (var n = 0; n < list.Length; n++)
                    list[n] = (UInt32)random.Next(Int32.MinValue, Int32.MaxValue);

                // radix sort
                var radixSortResult = (IList<UInt32>)list.Clone();
                sw.Reset();
                sw.Start();
                RadixSort(radixSortResult);
                sw.Stop();
                radixSortTicks += sw.ElapsedTicks;

                // comb sort
                var combSortResult = (IList<UInt32>)list.Clone();
                sw.Reset();
                sw.Start();
                CombSort(combSortResult);
                sw.Stop();
                combSortTicks += sw.ElapsedTicks;

                // Array.Sort
                var arraySortResult = list.ToArray();
                sw.Reset();
                sw.Start();
                Array.Sort(arraySortResult);
                sw.Stop();
                arraySortTicks += sw.ElapsedTicks;

                // correctness
                for (var n = 0; n < size; n++)
                {
                    if (radixSortResult[n] != arraySortResult[n])
                        Console.WriteLine("radixSortResult[{0}]: {1}, arraySortResult[{0}]: {2}", n, radixSortResult[n], arraySortResult[n]);
                    if (combSortResult[n] != arraySortResult[n])
                        Console.WriteLine("combSortResult[{0}]: {1}, arraySortResult[{0}]: {2}", n, combSortResult[n], arraySortResult[n]);
                }
            }

            Console.WriteLine("radix sort: {0} ({1:F})", radixSortTicks / count, radixSortTicks / (double)arraySortTicks);
            Console.WriteLine("comb sort: {0} ({1:F})", combSortTicks / count, combSortTicks / (double)arraySortTicks);
            Console.WriteLine("Array.Sort: {0} ({1:F})", arraySortTicks / count, arraySortTicks / (double)arraySortTicks);
        }


        static void RadixSort(IList<UInt32> list)
        {
            var tables = new int[sizeof(UInt32)][];
            for (var p = 0; p < tables.Length; p++)
                tables[p] = new int[0xFF + 1];

            // histgramming
            foreach (var x in list)
            {
                var y = x;
                for (var p = 0; p < tables.Length; p++)
                {
                    tables[p][(y + 1) & 0xFF]++;
                    y = y >> 8;
                }
            }

            // sum the histgrams
            foreach (var table in tables)
            {
                table[0] = 0;
                for (var n = 1; n < table.Length; n++)
                    table[n] += table[n - 1];
            }

            // read/write histgram, copy
            IList<UInt32> array = new UInt32[list.Count];
            Action swap = () => { var temp = list; list = array; array = temp; };
            for (var p = 0; p < tables.Length; p++)
            {
                var table = tables[p];
                foreach (var x in list)
                {
                    var y = (x >> p * 8) & 0xFF;
                    array[table[y]] = x;
                    table[y]++;
                }
                swap();
            }
        }

        static void CombSort(IList<UInt32> list)
        {
            const double shrinkFactor = 1.247330950103979; // 1.0 / (1.0 - 1.0 / Math.Pow(Math.E, Math.PI));
            var gap = list.Count;
            var swapped = true;
            while (gap > 1 || swapped)
            {
                if (gap > 1)
                    gap = (int)(gap / shrinkFactor);
                swapped = false;
                for (int i = 0; i + gap < list.Count; i++)
                {
                    if (list[i].CompareTo(list[i + gap]) > 0)
                    {
                        var t = list[i];
                        list[i] = list[i + gap];
                        list[i + gap] = t;
                        swapped = true;
                    }
                }
            }
        }
    }
}

ksksts / junk / source — bitbucket.org

結果は次の通り。
適当に比較したときは処理時間がArray.Sortの2倍以上で話にならないと思っていたけど、要素数が膨大になるにつれてそれなりに差が小さくなってきて少し嬉しい。
comb sortは遅いけどバブルソートの改良版と考えるとそれなりに良いような気がする。

size: 1000
radix sort: 3541 (2.88)
comb sort: 27689 (22.50)
Array.Sort: 1230 (1.00)
size: 10000
radix sort: 20451 (1.68)
comb sort: 417744 (34.33)
Array.Sort: 12167 (1.00)
size: 100000
radix sort: 207950 (1.45)
comb sort: 5288921 (36.95)
Array.Sort: 143143 (1.00)
size: 1000000
radix sort: 2081360 (1.30)
comb sort: 65056745 (40.50)
Array.Sort: 1606207 (1.00)