ТЕМА 10

//10.12.2020 Classwork MergeSort//

import java.util.Scanner;
import java.util.Arrays;

public class MergeSort {

    public static void Divide(int[] ARR, int l, int r){
        if(l < r){
            int m = (l + r)/2;//middle point//
            Divide(ARR, l,m); //sort left array//
            Divide(ARR, m+1, r); //sort right array//

            CompareAndMerge(ARR, l, m, r);//merge the arrays//
        }
    }//end of Divide//

    private static void CompareAndMerge(int[] arr, int l, int m, int r){
        int LeftArrLength = m - l + 1;
        int RightArrLength = r - m; //!!!//

        int[] L = new int[LeftArrLength];
        int[] R = new int[RightArrLength];

        for (int i = 0; i < LeftArrLength; i++) {
            L[i] = arr[l + i];
        }

        for (int j = 0; j < RightArrLength; j++) {
            R[j] = arr[m + 1 + j];
        }

        int i = 0;
        int j = 0;
        int k = l;

        while(i < LeftArrLength && j < RightArrLength){
            if(L[i] <= R[j]){
                arr[k] = L[i];
                i++;
            }else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while(i < LeftArrLength){
            arr[k] = L[i];
            i++;
            k++;
        }

        while(j < RightArrLength){
            arr[k] = R[j];
            j++;
            k++;
        }
    }//end of CompareAndMerge//

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter number of elements: ");
        int N = scan.nextInt();
        int[] ARR = new int[N];
        for (int i = 0; i < N; i++) {
            System.out.print("Enter element " + i + " :");
            ARR[i] = Integer.parseInt(scan.next());
        }
        //print before//
        System.out.println("BEFORE SORT: " + Arrays.toString(ARR));

        Divide(ARR, 0, ARR.length -1);

        //print after//
        System.out.println("BEFORE SORT: " + Arrays.toString(ARR));
    }//end of main//
}//end of class//