using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Counting sort");

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

        var sortedArr = CountingSort(arr);

        for(var i = 0; i < sortedArr.Length; i++)

        {

            Console.Write(sortedArr[i] + ", ");

        }

    }

    public static int[] CountingSort(int[] arr)

    {

        if(arr.Length <= 0)

        {

            return arr;

        }

        var max = arr[0];

        //Get max value in array

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

        {

            max = Math.Max(arr[i], max);

        }

        var countArr = new int[max + 1];

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

        {

            countArr[arr[i]]++;

        }

        var index = 0;

        for(var i = 0; i < countArr.Length; i++)

        {

            for(var j = 0; j < countArr[i]; j++)

            {

                arr[index] = i;

                index++;

            }

        }

        return arr;

    }

}