MergeSort.java

import java.util.Scanner;
class MergeSort {
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
            System.out.println("Enter the size:");
            int size = scan.nextInt();
            int arr[] = new int[size];
            for(int i=0;i<size;i++){
                arr[i] = scan.nextInt();
            }
            sort(arr);
            for(int i=0;i<size;i++){
                System.out.print(arr[i]+" ");
            }
    }

    static void sort(int arr[]){
        int n = arr.length;
        if(n<2){
            return;
        }
        int i;
        int mid = n/2;
        int leftArr[] = new int[mid];
        int rightArr[] = new int[n-mid];
        for(i=0;i<mid;i++){
            leftArr[i] = arr[i];
        }
        for(i=mid;i<n;i++){
            rightArr[i-mid] = arr[i];
        }
        sort(leftArr);
        sort(rightArr);
        merge(leftArr,rightArr,arr);
    }
    static void merge(int leftArr[],int rightArr[], int arr[]){
        int nL = leftArr.length;
        int nR = rightArr.length;
        int i=0,j=0,k=0;
        while(i<nL && j<nR){
            if(leftArr[i] < rightArr[j]){
                arr[k] = leftArr[i];
                i++;
            }
            else{
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }
        while(i<nL){
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        while(j<nR){
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }
}