Count sort - yehhaaa!

Count sort is very good to sort sequence of integer which has small range of values (in comparison with sequence length). Due to two assumptions - our sequence contains only integers and its values range is much less than amount of items in sequence, it's linear in time to the amount of items in input. It's much better than classic algorythms based on comparison, cause it doesn't use comparison in its work, so it overcomes traditional for comparing algorythms O(nlogn). Here is an implementation: Show/Hide

 using System;  
 using System.Collections.Generic;  
 using System.Linq;  
 using System.Text;  
 namespace CountSort  
 {  
     public class SortManager  
     {  
         public int[] Sort(int[] data)  
         {  
             int max = 0;  
             int min = 0;  
             // get min and max elements of input array to get borders of counting array  
             GetMaxMin(data, out min, out max);  
             // declare sorting array  
             int[] metaCount = new int[max + 1 - min];  
             // count amount of each item in iput  
             foreach (int d in data)  
             {  
                 metaCount[d - min]++;  
             }  
             // rebuild sorting array to get end position of each item in sorted output  
             for (int i = 1; i < metaCount.Length; i++)  
             {  
                 metaCount[i] += metaCount[i - 1];  
             }  
             int[] returnValue = new int[data.Length];  
             // just fill output array  
             int currentInsertPosition = 0;  
             for (int i = 0; i < metaCount.Length; i++)  
             {  
                 for (; currentInsertPosition < metaCount[i]; currentInsertPosition++)  
                 {  
                     returnValue[currentInsertPosition] = i + min;  
                 }  
             }  
             return returnValue;  
         }  
         void GetMaxMin(int[] data, out int min, out int max)  
         {  
             if (data.Length == 1)  
             {  
                 min = data[0];  
                 max = data[0];  
                 return;  
             }  
             decimal mediana = data.Length / 2;  
             int[] left = new int[(int)Math.Floor(mediana)];  
             int[] right = new int[data.Length - left.Length];  
             for (int i = 0; i < left.Length; i++)  
             {  
                 left[i] = data[i];  
             }  
             for (int i = 0; i < right.Length; i++)  
             {  
                 right[i] = data[i + left.Length];  
             }  
             int leftMin = 0;  
             int leftMax = 0;  
             int rightMin = 0;  
             int rightMax = 0;  
             GetMaxMin(left, out leftMin, out leftMax);  
             GetMaxMin(right, out rightMin, out rightMax);  
             min = leftMin < rightMin ? leftMin : rightMin;  
             max = leftMax > rightMax ? leftMax : rightMax;  
         }  
     }  
 }  

and of course some test for you:

 using System;  
 using System.Collections.Generic;  
 using System.Linq;  
 using System.Text;  
 using NUnit;  
 using NUnit.Framework;  
 namespace CountSort.Fixture  
 {  
     public class SortManagerTest  
     {  
         [Test]  
         public void TestFromZero()  
         {  
             SortManager manager = new SortManager();  
             int[] data = new[] { 1, 3, 0, 2, 1, 4, 3, 0, 2, 4, 2, 4, 3, 2, 1, 0 };  
             int[] sorted = manager.Sort(data);  
             checkSort(data, sorted);  
         }  
         [Test]  
         public void TestFromLessZero()  
         {  
             SortManager manager = new SortManager();  
             int[] data = new[] { 1, 3, 0, -1, 2, 1, 4, 3, 0, -1, -2 ,2, 4, 2, 4, -2, 3, -1, 2, 1, 0 };  
             int[] sorted = manager.Sort(data);  
             checkSort(data, sorted);  
         }  
         [Test]  
         public void TestFromGreatZero()  
         {  
             SortManager manager = new SortManager();  
             int[] data = new[] { 1, 3, 5, 1, 2, 1, 4, 3, 5, 11, 2, 2, 4, 2, 4, 2, 3, 1, 2, 1, 6 };  
             int[] sorted = manager.Sort(data);  
             checkSort(data, sorted);  
         }  
         [Test]  
         public void TestWithSpaces()  
         {  
             SortManager manager = new SortManager();  
             int[] data = new[] { 3, 3, 1, 1, 3, 5, 3, 1, 5, 6, 3, 1 };  
             int[] sorted = manager.Sort(data);  
             checkSort(data, sorted);  
         }  
         void checkSort(int[] input, int[] output)  
         {  
             // check both arrays have equal amount of items  
             Assert.AreEqual(output.Length, input.Length);  
             // check for sort  
             for (int i = 1; i < output.Length; i++)  
             {  
                 Assert.IsTrue(output[i - 1] <= output[i]);  
             }  
             // check no new items in output  
             for (int i = 0; i < output.Length; i++)  
             {  
                 bool isInInput = false;  
                 foreach (int inp in input)  
                 {  
                     if (output[i] == inp)  
                     {  
                         isInInput = true;  
                         break;  
                     }  
                 }  
                 Assert.IsTrue(isInInput);  
             }  
             // check no items lost  
             for (int i = 0; i < input.Length; i++)  
             {  
                 bool isInOutput = false;  
                 foreach (int outp in output)  
                 {  
                     if (input[i] == outp)  
                     {  
                         isInOutput = true;  
                         break;  
                     }  
                 }  
                 Assert.IsTrue(isInOutput);  
             }  
             // check sum  
             int sumInput = 0;  
             for (int i = 0; i < input.Length; i++)  
             {  
                 sumInput += input[i];  
             }  
             int sumOutput = 0;  
             for (int i = 0; i < output.Length; i++)  
             {  
                 sumOutput += output[i];  
             }  
             Assert.AreEqual(sumInput, sumOutput);  
         }  
     }  
 }