using System;
using System.Text;

namespace sortowania_konsola
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] tablica = new int[] { 1, 0, 8, 4, 2, 5, 3 };
            //int[] tablica2 = new double[] { 1.5, 0.7, 8, 4, 2, 5, 3.3 };
            //BubbleSort(tablica);
            //int[] posortowana = Zliczanie(tablica);
            //Zliczanie(tablica);
            //Wybieranie(tablica);
            //Wstawianie(tablica);
            /*foreach (int liczba in posortowana)
            {
                Console.WriteLine(liczba);
            }*/
            //Szybkie(tablica, 0, tablica.Length - 1);
            MergeSort(tablica, 0, tablica.Length - 1);
            foreach (int liczba in tablica)
            {
                Console.Write(liczba + " ");
            }
            Console.ReadKey();
        }

        static int[] BubbleSort(int[] array)
        {
            int tmp;
            for (int i = 0; i < array.Length; i++)
            {
                for (int j = 0; j < array.Length - 1; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        tmp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = tmp;
                    }
                }
            }
            return array;
        }

        static int[] CountingSort(int[] array)
        {
            int[] sorted = new int[array.Length];
            int minVal = array[0];
            int maxVal = array[0];
            for (int i = 1; i < array.Length; i++)
            {
                if (array[i] < minVal) minVal = array[i];
                else if (array[i] > maxVal) maxVal = array[i];
            }

            int[] counts = new int[maxVal - minVal + 1];

            for (int i = 0; i < array.Length; i++)
            {
                counts[array[i] - minVal]++;
            }

            counts[0]--;

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

            for (int i = array.Length - 1; i >= 0; i--)
            {
                sorted[counts[array[i] - minVal]--] = array[i];
            }
            return sorted;
        }

        static int[] SelectionSort(int[] array)
        {
            int i, j, min, tmp;
            for (i = 0; i < array.Length; i++)
            {
                min = i;
                for (j = 0; j < array.Length; j++)
                {
                    if (array[j] > array[min])
                    {
                        min = j;
                        tmp = array[j];
                        array[j] = array[i];
                        array[i] = tmp;
                    }
                }
            }
            return array;
        }

        static int[] InsertionSort(int[] array)
        {
            int j, tmp;
            for (int i = 0; i < array.Length; i++)
            {
                tmp = array[i];
                j = i - 1;
                while (j >= 0 && array[j] > tmp)
                {
                    array[j + 1] = array[j];
                    j--;
                }
                array[j + 1] = tmp;
            }
            return array;
        }

        static void QuickSort(int[] array, int left, int right)
        {
            var i = left;
            var j = right;
            var pivot = array[(left + right) / 2];
            while (i < j)
            {
                while (array[i] < pivot) i++;
                while (array[j] > pivot) j--;
                if (i <= j)
                {
                    var tmp = array[i];
                    array[i++] = array[j];
                    array[j--] = tmp;
                }
            }
            if (left < j) QuickSort(array, left, j);
            if (i < right) QuickSort(array, i, right);
        }

        static void Merge(int[] input, int left, int middle, int right)
        {
            int[] leftArray = new int[middle - left + 1];
            int[] rightArray = new int[right - middle];

            Array.Copy(input, left, leftArray, 0, middle - left + 1);
            Array.Copy(input, middle + 1, rightArray, 0, right - middle);

            int i = 0;
            int j = 0;
            for (int k = left; k < right + 1; k++)
            {
                if (i == leftArray.Length)
                {
                    input[k] = rightArray[j];
                    j++;
                }
                else if (j == rightArray.Length)
                {
                    input[k] = leftArray[i];
                    i++;
                }
                else if (leftArray[i] <= rightArray[j])
                {
                    input[k] = leftArray[i];
                    i++;
                }
                else
                {
                    input[k] = rightArray[j];
                    j++;
                }
            }
        }

        static void MergeSort(int[] input, int left, int right)
        {
            if (left < right)
            {
                int middle = (left + right) / 2;

                MergeSort(input, left, middle);
                MergeSort(input, middle + 1, right);

                Merge(input, left, middle, right);
            }
        }
    }
}