using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace tims6Olga
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new int[6000000];
            Random rd = new Random();


            for (int i = 0; i < arr.Length; ++i)
            {
                arr[i] = rd.Next(0, 100);
            }

            for (int i = 0; i < 3; i++)
            {
                Sort(arr, min(arr), max(arr));
            }

            for (int i = 0; i < 10; i++)
            {
                Sort(arr, min(arr), max(arr));
            }


            Console.ReadLine();

        }

        private static int min(int[] arr)
        {
            int min = Int32.MaxValue;
            foreach (var buf in arr)
            {
                if (buf < min)
                {
                    min = buf;
                }
            }

            return min;
        }

        private static int max(int[] arr)
        {
            int max = Int32.MinValue;
            foreach (var buf in arr)
            {
                if (buf > max)
                {
                    max = buf;
                }
            }

            return max;
        }
        private static void Sort(int[] arr, int min, int max)
        {
            var startTime = System.Diagnostics.Stopwatch.StartNew();

            int[] count = new int[max - min + 1];
            int z = 0;

            for (int i = 0; i < count.Length; i++)
            {
                count[i] = 0;
            }

            for (int i = 0; i < arr.Length; i++)
            {
                count[arr[i] - min]++;
            }

            for (int i = min; i <= max; i++)
            {
                while (count[i - min]-- > 0)
                {
                    arr[z] = i;
                    z++;
                }
            }

            var resultTime = startTime.Elapsed;

            string elapsedTime = String.Format("{0:00}.{1:000}",
                resultTime.Seconds,
                resultTime.Milliseconds);
            Console.WriteLine("Timea = " + elapsedTime);

        }
    }
}