using System;

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

namespace ConsoleApp3
{
    class MergeSort
    {

        public static void  sortowanie(int[] tab)
        {
            int liczbaPrzedzialow;
            int from=0;
            int przedzial1 = 1;
            int przedzial2 = 1;
            bool parzysta = tab.Length % 2 == 0 ? true : false;
            int n = 1;
            if (parzysta)
            {

            }
            while (przedzial1 < tab.Length)
            {
                from = 0;
                n = 1;
                for( ; ; )
                {
                     if (przedzial1 * n < tab.Length)
                    {
                        scalanie(tab, from, przedzial1, przedzial1);
                        from = from + przedzial1*2;
                        n++;
                        continue;
                    }
                    przedzial2 = tab.Length - przedzial1*n;
                    scalanie(tab, from, przedzial1, przedzial2);
                    break;


                }
                przedzial1 = przedzial1 * 2;

            }

        }

        public static void scalanie(int[] tab, int from1, int przedzial1, int przedzial2)
        {
            //int[] tabWynikowa = new int[tab1.Length + tab2.Length];
            int licznik = from1;
            int tab1Licznik = 0, tab2Licznik = 0;

            int tab1LicznikTo = from1 + przedzial1;
            int tab2LicznikTo = tab1LicznikTo + przedzial2;

            int[] tab1 = new int[przedzial1];
            int[] tab2 = new int[przedzial2];
            for (int i = from1; i < tab1LicznikTo; i++)
            {
                tab1[i - from1] = tab[i];
            }
            for (int i = tab1LicznikTo; i < tab2LicznikTo; i++)
            {
                tab2[i - tab1LicznikTo] = tab[i];
            }

            while (licznik < from1+ przedzial1+przedzial2)
            {

                if (tab1Licznik == przedzial1 && tab2Licznik < przedzial2)
                {

                    tab[licznik] = tab2[tab2Licznik];

                    tab2Licznik++;
                    licznik++;
                    continue;
                }
                if (tab2Licznik == przedzial2 && tab1Licznik < przedzial1)
                {
                    tab[licznik] = tab1[tab1Licznik];
                    tab1Licznik++;
                    licznik++;
                    continue;
                }
                if (tab1Licznik < przedzial1 && tab2Licznik < przedzial2 && tab1[tab1Licznik] < tab2[tab2Licznik])
                {
                    tab[licznik] = tab1[tab1Licznik];
                    tab1Licznik++;
                    licznik++;
                    continue;
                }
                if (tab1Licznik < przedzial1 && tab2Licznik < przedzial2 && tab1[tab1Licznik] > tab2[tab2Licznik])
                {

                    tab[licznik] = tab2[tab2Licznik];
                    tab2Licznik++;
                    licznik++;
                    continue;
                }

                if (tab1Licznik < przedzial1 && tab2Licznik < przedzial2 && tab1[tab1Licznik] == tab2[tab2Licznik])
                {

                    tab[licznik] = tab1[tab1Licznik];
                    tab1Licznik++;
                    licznik++;

                    tab[licznik] = tab2[tab2Licznik];
                    tab2Licznik++;
                    licznik++;
                    continue;
                }


            }

        }
    }
    class Sortowanie
    {
        public static int[] sortowanie(int[] tab)
        {
            int tmp;
            int licznik = 0;
            int n = 0;
            do
            {
                licznik = 0;
                for (int i = 0; i < tab.Length - 1; i++)
                {

                    if (tab[i] > tab[i + 1])
                    {
                        licznik++;
                        tmp = tab[i];
                        tab[i] = tab[i + 1];
                        tab[i + 1] = tmp;
                    }
                }
                n++;
            } while (licznik != 0);
            //Console.WriteLine();
            //Console.WriteLine(licznik);
            //Console.WriteLine();
            //Console.WriteLine(n);
            return tab;
        }
    }
    class Program
    {

        static void Main(string[] args)
        {
            Random r = new Random();
            int[] test1 = new int[3];
            for (int i = 0; i < test1.Length; i++)
            {
                test1[i] = r.Next(0, 40);
            }
            int[] test2 = new int[5];
            for (int i = 0; i < test2.Length; i++)
            {
                test2[i] = r.Next(0, 40);
            }

            //Console.WriteLine();
            //Console.WriteLine("----------------");
            //Console.WriteLine();
            //foreach (var item in test1)
            //{
            //    Console.Write(item + "  ");
            //}
            //Console.WriteLine();
            //Console.WriteLine("----------------");
            //Console.WriteLine();
            //foreach (var item in test2)
            //{
            //    Console.Write(item + "  ");
            //}
            //Console.WriteLine();
            //Console.WriteLine("----------------");
            //Console.WriteLine();
            //foreach (var item in test1)
            //{
            //    Console.Write(item + "  ");
            //}
            int[] posortowana1 = new int[10];
            int[] posortowana2 = new int[10];
            int[] scalona = new int[posortowana1.Length + posortowana2.Length];
            Console.WriteLine();
            Console.WriteLine();
            DateTime start = DateTime.Now;
            //posortowana1 = Sortowanie.sortowanie(test1);
            //posortowana2 = Sortowanie.sortowanie(test2);
            MergeSort.sortowanie(test1);


            DateTime stop = DateTime.Now;

            TimeSpan czas = stop - start;
            foreach (var item in test1)
            {
                Console.Write(item + "  ");
            }


            Console.WriteLine();
            Console.WriteLine("----------------");
            Console.WriteLine();
            start = DateTime.Now;
            //posortowana1 = Sortowanie.sortowanie(test1);
            //posortowana2 = Sortowanie.sortowanie(test2);
            Sortowanie.sortowanie(test2);


            stop = DateTime.Now;

            TimeSpan czas2 = stop - start;
            foreach (var item in test2)
            {
                Console.Write(item + "  ");
            }


            Console.WriteLine();
            Console.WriteLine("----------------");
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine("czas sortowania merge= " + czas);
            Console.WriteLine();
            Console.WriteLine("czas sortowania normal= " + czas2);
            Console.ReadKey();

        }
    }
}