START PROCEDURE
Merge (arr, l, mid, h )
    s1 ← mid−l+1
    s2 ← h-mid
    Create arrays temp_left[s1] and R[s2]
    FOR i ← 1 TO s1
        DO temp_left[i] ← arr[l + i ]
    END FOR      
    FOR j ← 1 TO s2
        DO temp_right[j] ← arr[q + j+1 ]
    END FOR
    i ← 0
    j ← 0
    k ← l
    WHILE i<s1 ^ j<s2 DO 
        IF temp_right[j ] ≤ temp_left[i]
            THEN arr[k] ← temp_right[j]
            j ← j + 1
        ELSE arr[k] ← temp_left[j]
            i ← i + 1
        END IF
    k ← k+1
    END WHILE
    WHILE i<s1 DO
        arr[k]=temp_left[i]
        i←i+1
        k←k+1
    END WHILE
    WHILE j<s2 DO
        arr[k]=temp_right[j]
        j←j+1
        k←k+1
    END WHILE
END PROCEDURE

START PROCEDURE
mergesort (arr,l,h)
    IF l<h THEN 
        mid←0
        mid←(l+h)/2
        mergesort(arr,l,mid)
        mergesort(arr,mid+1,h)
        Merge(arr,l,mid,h)
    END IF
END PROCEDURE

arr → Array
l → lower boundary of the array
h → higher boundary of the array
mid → Middle element of the array
mergesort() → Function to sort the elements
Merge() → Function to Merge the sorted elements
temp_left and temp_right → Temporary arrays for storing the left and right sub-arrays.

import java.util.*;
class MergeSort{

    static int n,i,j,k,step=0;
    static Scanner sc =new Scanner(System.in);
    
    static void Merge(int[] arr, int l, int mid, int h) {
        step++;
        int [] temp_left=new int[mid-l+1];
        int [] temp_right=new int[h-mid];
        int s1=temp_left.length;
        int s2=temp_right.length;

        for(i=0;i<s1;i++)
            temp_left[i]=arr[l+i];

        for(j=0;j<s2;j++)
            temp_right[j]=arr[mid+1+j];

        int i=0,j=0;
        int k=l;
        while(i<s1 && j<s2){
            if(temp_right[j]<=temp_left[i]){
                arr[k]=temp_right[j];
                j++;
            }
            else{
                arr[k]=temp_left[i];
                i++;
            }
            k++;
        }    
        while(i<s1){
            arr[k]=temp_left[i];
            i++;
            k++;
        }
        while(j<s2){
            arr[k]=temp_right[j];
            j++;
            k++;
        }
        System.out.print("\n At step " + step + " the sorted array is: ");
        for(k=0;k<=h;k++)
            System.out.print(arr[k] + " ");
    }

    static void mergesort(int [] arr,int l,int h){
        if(l<h){
            int mid=0;
            mid=(l+h)/2;
            mergesort(arr,l,mid);
            mergesort(arr,mid+1,h);
            Merge(arr,l,mid,h);
        }
    }
        public static void main(String [] args){
             System.out.println("Enter the size of the array: ");
             n=sc.nextInt();
             int[] arr=new int[n];
             System.out.println("Enter the elements of the array: ");
             for(i=0;i<n;i++)
                arr[i]=sc.nextInt();
             mergesort(arr, 0, n-1);
         }    
}