using System;
using System.Linq.Expressions;

namespace CountingSort {
    class Program {
        static void Main(string[] args) {
            int[] arr = new int[] {1, 2, 5, -1, -2, 3};
            Console.WriteLine(string.Join(", ", CountingSort(arr)));
        }

        public static int[] CountingSort(int[] array) {
            int[] counting = new int[GetMax(array) - GetMin(array) + 1];
            for (int i = 0; i < array.Length; i++) {
                counting[array[i] - GetMin(array)] += 1;
            }

            int[] numbersIndexes = new int[counting.Length];
            for (int i = 1; i < counting.Length; i++) {
                numbersIndexes[i] = numbersIndexes[i - 1] + counting[i - 1];
            }

            int[] sortedArray = new int[array.Length];
            for (int i = 0; i < array.Length; i++) {
                sortedArray[numbersIndexes[array[i] - GetMin(array)]++] = array[i];
            }

            return sortedArray;
        }


        public static int GetMin(int[] array) {
            int min = array.Length == 0 ? 0 : array[0];
            for (int i = 0; i < array.Length; i++) {
                if (array[i] < min) {
                    min = array[i];
                }
            }

            return min;
        }

        public static int GetMax(int[] array) {
            int max = array.Length == 0 ? 0 : array[0];
            for (int i = 0; i < array.Length; i++) {
                if (array[i] > max) {
                    max = array[i];
                }
            }

            return max;
        }
    }
}