import java.util.*;
import java.io.*;

class Merge{
	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.nextInt(medB - medA + 1) + medA;
		}
		return novaT;
	}

	public static int[] zlij(int[] tab1, int[] tab2)
	{
		/* 
			vrne zliti nepadajoče urejeni tabeli 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];
			System.arraycopy(tab, 0, rez, 0, tab.length); // lahko tudi s rez = tab.clone(); 
			return rez;
		}
		// na pol
		int[] prvaPol = new int[tab.length / 2];
		int[] drugaPol = new int[tab.length - tab.length / 2];
		System.arraycopy(tab, 0, prvaPol, 0, tab.length / 2);
		System.arraycopy(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++)
		{
			System.out.print(tab[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args)
	{
		int velikost = 0, odKje = 0, doKam = 0;
        
		Scanner sc = new Scanner(System.in);
	
		System.out.print("Kako velika je tabela: ");
		velikost = sc.nextInt();
		System.out.print("Sp. meja: ");
		odKje = sc.nextInt();
		System.out.print("Zg. meja: ");
		doKam = sc.nextInt();
		int[] tabela = ustvariTabelo(velikost, odKje, doKam);
		System.out.print("Originalna tabela:");
		izpisTabele(tabela);
		int[] urejena = urediZZlivanjem(tabela);
		System.out.print("Urejena:");
		izpisTabele(urejena);
	}
}