import java.util.*;
 
 
public class Sort{
        public static void main (String[] args){
                Scanner myScanner = new Scanner(System.in);
                System.out.println("Enter the size of an erray: ");
                int size = myScanner.nextInt();
                int[] firstArray = new int[size];
                System.out.println("Enter the item of array;");
                for(int i=0; i<size; i++){
                        firstArray[i] = myScanner.nextInt();
                }
                int sizeM = size/2;
 
                int[] firstHalf; 
                int[] secondHalf; 
 
                if((size%2) == 0){
                        firstHalf = new int[sizeM]; 
                        secondHalf = new int[sizeM]; 
                        for(int i=0; i<sizeM; i++){
                                firstHalf[i] = firstArray[i];
                                secondHalf[i] = firstArray[i+sizeM];
                        }
                }
 
                else{
                        firstHalf = new int[sizeM];
                        secondHalf = new int[sizeM+1];
                        for(int i=0; i<sizeM; i++){
                                firstHalf[i] = firstArray[i];
                        }
                        for(int i=0; i<sizeM+1; i++){
                                secondHalf[i] = firstArray[i+sizeM];
                        }
                }
                System.out.println(" first half of an array ");
                for(int i=0; i<firstHalf.length;i++){
                        System.out.print(firstHalf[i]+ " ");
                }
                System.out.println("");
                System.out.println(" second half of an array ");
                for(int i=0; i<secondHalf.length;i++){
                        System.out.print(secondHalf[i] + " " );
                }
 
                Thread thread1 = new Thread(new MergeTask(firstHalf)); 
                Thread thread2 = new Thread(new MergeTask(secondHalf)); 
                Thread thread3 = new Thread(new MergeTask(firstHalf, secondHalf)); 
                System.out.println(" ");
                System.out.println(" Sorted arrays " );
 
                thread1.start();                
                try { 
                        thread1.join(); 
                }
                catch(InterruptedException ex) { } 
 
                thread2.start();
                try{ 
                        thread2.join(); 
                }
                catch(InterruptedException ex) { } 
 
                thread3.start(); 
                try { 
                        thread3.join(); 
                }
                catch(InterruptedException ex) { }
        }
}
 
 
class MergeTask extends Thread{ 
        int[] nums; 
        MergeTask(int[] n){
                nums = n; 
        } 
 
        MergeTask(int[] x, int[] y){
                int middle = x.length; 
                nums = new int[x.length + y.length]; 
                for(int i = 0; i < (x.length + y.length); i++){ 
                        if(i < middle){ 
                                nums[i] = x[i]; 
                        } 
                        else{ 
                                nums[i] = y[i - middle]; 
                        } 
                } 
        } 
 
        public void run() { 
                Arrays.sort(this.nums); 
                for(int i = 0; i < nums.length; i++) { 
                        System.out.print(nums[i] + " "); 
                }
                System.out.println(); 
        } 
}