import java.util.*;
class ms{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        System.out.println("Enter number of terms : ");
        int n = s.nextInt();
        int[] arr = new int[n];
        System.out.println("enter the numbers : ");
        for(int i=0;i<n;i++){
            arr[i] = s.nextInt();
        }
        System.out.println("unsorted array: " + Arrays.toString(arr));
        mergeSort(arr);// we are passing our array to the mergesort() function as input
        System.out.println("sorted array : ");
        for(int i=0;i<n;i++){
            System.out.println(arr[i]);
        }
    }
    public static void mergeSort(int[] arr){
        int n = arr.length;
        if(n<2)return;
        int mid = n / 2;
        int[] l = new int[mid];
        int[] r = new int[n-mid];
        for(int i=0;i<mid;i++){
            l[i] = arr[i];
        }
        for(int i=mid;i<n;i++){
            r[i-mid] = arr[i];
        }
        mergeSort(l);
        mergeSort(r);
        merge(arr,l,r);
    }
    public static void merge(int[] arr, int[] l,int[] r){
        int nL = l.length;
		int nR = r.length;
		int i = 0, j = 0, k = 0;
        /*
        if l = [3,2,1];
        if r = [6,7,8];
        then after entering the while loop,compare the elements of l & r arrays,
        if l<r, then replace the arr[k] with the lth element && increment i by 1
        else replace it with rth element && increment j by 1
        next, we have to check whether there are any leftovers in the left & right arrays.
        thats it, we have to do it recursively for both the left and right arrays.
        Strengths:
            Fast. Merge sort runs in
            O(nlog(n))
            O(nlog(n)), which scales well as n grows.
            Parallelizable. Merge sort breaks the input into chunks,
            each of which can be sorted at the same time in parallel.
        Weaknesses:
            Space. Merge sort takes up O(n) extra space, including
            O(lg(n)) space for the recursive call stack.
        Time complexity of Merge Sort is  θ(nLogn) in all 3 cases
        (worst, average and best) as merge sort always divides the array into two halves
        and takes linear time to merge two halves.
        Auxiliary Space: O(n)
        
        Algorithmic Paradigm: Divide and Conquer
        Sorting In Place: No in a typical implementation
        Stable: Yes
        */
		while(i<nL && j<nR){
            if(l[i]<=r[j]){
                arr[k] = l[i];
                i++;
            }
            else{
                arr[k] = r[j];
                j++;
            }
            k++;
        }
        while(i<nL){
            arr[k] = l[i];
            i++;
            k++;
        }
        while(j<nR){
            arr[k] = r[j];
            j++;
            k++;
        }
    }