Counting sort review

Question

I've just wrote a program in C# for counting sort.

• space complexity is O(N+K)
• time complexity is O(N+K)

I want reviews on my code and any better ways to implement this.

namespace SortingSelfCoded
{
 public static class CountingSorter
 {
 public static int[] CountingSort(int [] input)
 {
 // O(1)
 int max = input[0];
 // O(N)
 for (int i = 0; i < input.Length; i++)
 {
 if (input[i] > max)
 {
 max = input[i];
 }
 }
 // Space complexity O(N+K)
 int[] counts = new int[max + 1];
 int[] output = new int[input.Length];
 // O(N)
 for (int i = 0; i < input.Length; i++)
 {
 counts[input[i]]++;
 }
 int j=0;
 // O(N+K)
 for (int i = 0; i < counts.Length; i++)
 {
 while (counts[i] > 0)
 {
 output[j] = i;
 j++;
 counts[i]--;
 }
 }
 return output;
 }
 }
}

Answer 1

From a practical use point of view:

1. I'd use input.Max() (LINQ) to obtain the maximum. Less code to write and does the same.
2. While it is ok to use single letter variables for loop counter j is not really a loop counter. It's the index of the current element so I would rename j into currentIndex.

3. Consider changing your last while loop into a for loop. This avoids mutating the state of the count array (saves you a read and write on every iteration):

   for (int k = 0; k < count[i]; k++)
   {
    output[currentIndex++] = i;
   }
   

4. Even on a 64 bit system the size of an array is limited to 2GB. So if your largest key is in the vicinity of Int32.Max / 4 or larger then you will get an OutOfMemoryException. Depending what else you are doing in your program you will get it much earlier. If you are experimenting around with sorting algorithms then there are some interesting approaches reducing the key space.