using System;

​

class Program

{

    static void Main(string[] args)

    {

        int[] arr = { 7, 1, 2, 8, 9, 9, 4, 1, 5, 5 };

        int[] sortedArr = CountingSort(arr);

​

        Console.WriteLine("Original array: [{0}]", string.Join(", ", arr));

        Console.WriteLine("Sorted array: [{0}]", string.Join(", ", sortedArr));

    }

​

    static int[] CountingSort(int[] arr)

    {

        int[] sortedArr = new int[arr.Length];

        int[] countArr = new int[arr.Length];

​

        for (int i = 0; i < arr.Length; i++)

        {

            countArr[arr[i]]++;

        }

​

        for (int i = 1; i < countArr.Length; i++)

        {

            countArr[i] += countArr[i - 1];

        }

​

        for (int i = arr.Length - 1; i >= 0; i--)

        {

            sortedArr[countArr[arr[i]] - 1] = arr[i];

            countArr[arr[i]]--;

        }

​

        return sortedArr;

    }

}

​

​