//Sortowanie przez scalanie (mergesort)
    //www.algorytm.org
    class Program
    {
        const int N = 100; //rozmiar tablicy do posortowania
        static int[] tablica = new int[N]; //tablica do posortowania
        static int[] tab = new int[N]; //tablica pomocnicza

        /// <summary>
        /// Scalanie tablic:
        /// pierwsza tablica ma indeksy od "pocz" do ("pocz" + "kon") / 2
        /// druga tablica ma indeksy od (("pocz" + "kon") / 2) + 1 do "kon"
        /// </summary>
        /// <param name="pocz">poczatek pierwszej tablicy</param>
        /// <param name="kon">koniec drugiej tablicy</param>
        static void scalanie(int pocz, int kon)
        {
            //Skopiuj wartosci do tablicy pomocniczej
            for (int i = pocz; i <= kon; i++)
            {
                tab[i] = tablica[i];
            }

            //Scalaj tablice
            int p = pocz;
            int q = (pocz + kon) / 2 + 1;
            int r = pocz;
            while (p <= (pocz + kon) / 2 && q <= kon)
            {
                if (tab[p] < tab[q])
                {
                    tablica[r] = tab[p];
                    r++;
                    p++;
                }
                else
                {
                    tablica[r] = tab[q];
                    r++;
                    q++;
                }
            }

            //Przepisz koncowke
            while (p <= (pocz + kon) / 2)
            {
                tablica[r] = tab[p];
                r++;
                p++;
            }
        }

        /// <summary>
        /// Sortowanie przez scalanie (mergesort)
        /// </summary>
        /// <param name="pocz">indeks poczatkowy tablicy do sortowania</param>
        /// <param name="kon">indeks koncowy tablicy do sortowania</param>
        static void sortowanie(int pocz, int kon)
        {
            if (pocz < kon)
            {
                //podziel sortowana tablice na pol
                sortowanie(pocz, (pocz + kon) / 2);
                sortowanie((pocz + kon) / 2 + 1, kon);
                //scal posortowane tablice
                scalanie(pocz, kon);
            }
        }

        /// <summary>
        /// Program
        /// </summary>
        static void Main()
        {
            //Wypelnij tablice losowymi wartosciami
            Random r = new Random();
            for (int i = 0; i < N; i++)
            {
                tablica[i] = r.Next(1001);
            }

            //Wypisz nie posortowana tablice
            for (int i = 0; i < N; i++)
            {
                Console.Write("{0} ", tablica[i]);
            }

            //Sortuj tablice uzywajac sortowania przez scalanie (mergesort)
            sortowanie(0, N - 1);

            //Wypisz posortowana tablice
            Console.WriteLine("\n");
            for (int i = 0; i < N; i++)
            {
                Console.Write("{0} ", tablica[i]);
            }
            Console.ReadLine();
        }
    }