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

namespace MergeSort
{
    class Program
    {
        public static int[] UstvariTabelo(int n, int medA, int medB)
        {
            /// naredimo tabelo/seznam velikosti n iz celih števil medA in medB
            int[] novaT = new int[n];
            Random gen = new Random();
            for (int i = 0; i < n; i++)
            {
                novaT[i] = gen.Next(medA, medB + 1);
            }
            return novaT;
        }
        public static int[] Zlij(int[] tab1, int[] tab2)
        {
            /// vrni zliti nepadajoče urejeni tabeli/seznama tab1 in tab2
            int[] novaT = new int[tab1.Length + tab2.Length];
            int kjePrva = 0; // kje smo v prvi tabeli
            int kjeDruga = 0; // kje v drugi
            int kjeNova = 0; // kam dajemo v novo
            while (kjePrva < tab1.Length && kjeDruga < tab2.Length)
            {
                if (tab1[kjePrva] < tab2[kjeDruga])
                {
                    novaT[kjeNova] = tab1[kjePrva];
                    kjePrva++;
                    kjeNova++;
                }
                else
                {
                    novaT[kjeNova] = tab2[kjeDruga];
                    kjeDruga++;
                    kjeNova++;
                }
            }
            // prepišemo ostanke
            while (kjePrva < tab1.Length)
            {
                novaT[kjeNova] = tab1[kjePrva];
                kjePrva++;
                kjeNova++;
            }
            while (kjeDruga < tab2.Length)
            {
                novaT[kjeNova] = tab2[kjeDruga];
                kjeDruga++;
                kjeNova++;
            }
            return novaT;
        }
        public static int[] UrediZZlivanjem(int[] tab)
        {
            if (tab.Length < 2)
            {
                int[] rez = new int[tab.Length];
                Array.Copy(tab, rez, tab.Length);
                return rez;
            }
            // na pol
            int[] prvaPol = new int[tab.Length / 2];
            int[] drugaPol = new int[tab.Length - tab.Length / 2];
            Array.Copy(tab, prvaPol, tab.Length / 2);
            Array.Copy(tab, tab.Length / 2, drugaPol, 0, drugaPol.Length);
            int[] urejenaPrva = UrediZZlivanjem(prvaPol);
            int[] urejenaDruga = UrediZZlivanjem(drugaPol);
            int[] urejena = Zlij(urejenaPrva, urejenaDruga);
            return urejena;
        }
        public static void IzpisTabele(int[] tab)
        {
            for (int i = 0; i < tab.Length; i++)
            {
                Console.Write(tab[i] + " ");
            }
            Console.WriteLine();
        }

        static void Main(string[] args)
        {
            int velikost, odKje, doKam;
            Console.Write("Kako velika je tabela: ");
            velikost = int.Parse(Console.ReadLine());
            Console.Write("Sp. meja: ");
            odKje = int.Parse(Console.ReadLine());
            Console.Write("Zg. meja: ");
            doKam = int.Parse(Console.ReadLine());
            int[] tabela = UstvariTabelo(velikost, odKje, doKam);
            Console.Write("Originalna tabela:");
            IzpisTabele(tabela);
            int[] urejena = UrediZZlivanjem(tabela);
            Console.Write("Urejena:");
            IzpisTabele(urejena);
        }
    }
}
