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

namespace SortowaniePrzezScalanie
{
    class Program
    {
        static void Scalanie(int[] tab, int lewy, int środek, int prawy)
        {
            //stores the starting position of both parts in temporary variables.
            int startLewej = lewy, startPrawej = środek + 1;

            int[] tabPomocnicza = new int[prawy - lewy + 1];
            int k = 0;

            for (int i = lewy; i <= prawy; i++)
            {
                if (startLewej > środek)      //checks if first part comes to an end or not .
                    tabPomocnicza[k++] = tab[startPrawej++];

                else if (startPrawej > prawy)   //checks if second part comes to an end or not
                    tabPomocnicza[k++] = tab[startLewej++];

                else if (tab[startLewej] < tab[startPrawej])     //checks which part has smaller element.
                    tabPomocnicza[k++] = tab[startLewej++];

                else
                    tabPomocnicza[k++] = tab[startPrawej++];
            }
            for (startLewej = 0; startLewej < k; startLewej++)
            {
                /* Now the real array has elements in sorted manner including both
                     parts.*/
                tab[lewy++] = tabPomocnicza[startLewej];
            }
        }

        static void Sortowanie(int[] tab, int lewy, int prawy)
        {
            if (lewy < prawy)
            {
                int środek = (lewy + prawy) / 2;           // defines the current array in 2 parts .
                Sortowanie(tab, lewy, środek);                 // sort the 1st part of array .
                Sortowanie(tab, środek + 1, prawy);              // sort the 2nd part of array.

                // merge the both parts by comparing elements of both the parts.
                Scalanie(tab, lewy, środek, prawy);
            }
        }

        static void Main(string[] args)
        {
            int[] tab = { 23, 11, 45, 58, 17 };
            Sortowanie(tab, 0, tab.Length - 1);
            foreach (var item in tab)
            {
                Console.Write(item + " ");
            }
            Console.ReadKey();
        }
    }
}