MERGE-SORT Algorithm (JAVA Program)

Today I am going to share the code for the Divide and Conquer Algorithm, Merge-Sort.
The Algorithm uses the Recursive call to itself and in the end a call to the merge subroutine that combines the two sorted lists.

For example if we have a list of 9 elements:
12, 34, 56, 97, 10, 5, 15, 45, 100

We pass the list to mergesort(int arr[], int p, int r) procedure/function/method where p is the start index (0 according to our example) and r is the end index (n-1, according to our example). This method in turn finds out the middle index as q=(p+r)/2, thus partitioning the original list into two halves for which the mergesort procedure is called recursively as mergesort(int arr[], int p, int q) and mergesort(int arr[], int q+1, int r). Finally we merge the elements in the absolute inner loop when only 2 elements are left to be  merged and then we keep on reaching the outer loop with the merge procedure in each step.
This can be expressed using the following diagram:

The Java Program for Merge sort is provided below:

Merge-Sort (JAVA Program)

package javaapplication1;

import java.util.Scanner;

public class MergeSort1 {

    public static void main(String[] args) {

        Scanner obj=new Scanner(System.in);

        System.out.println("Enter number of elements = ");

        int n=obj.nextInt();

        System.out.println("Enter "+n+" elements = ");

        int arr[]=new int[n];

        for(int i=0;i<n;i++){

            arr[i]=obj.nextInt();

        }

        int p=0;int r=n-1;

        mergesort(arr,p,r);

        for(int i=0;i<n;i++)

        System.out.println(arr[i]);

    }

    

    static void mergesort(int a[],int p, int r){

        if(p<r){

            int q=(p+r)/2;

            mergesort(a, p, q);

            mergesort(a, q+1, r);

            merge(a,p,q,r);

        }

       

    }

    

    static void merge(int a[],int p, int q, int r){

        int n1=q-p+1;

        int n2=r-q;

        int arr1[]=new int[n1];

        int arr2[]=new int[n2];

        for(int i=0;i<n1;i++){

            arr1[i]=a[p+i];

        }

        for(int j=0;j<n2;j++){

            arr2[j]=a[q+j+1];

        }

        

        int i=0;

        int j=0;

        for(int k=p;k<r+1;k++){

            if(i==n1){

                a[k]=arr2[j];

                j++;

                continue;

            }

            if(j==n2){

                a[k]=arr1[i];

                i++;

                continue;

            }

            if(arr1[i]<=arr2[j]&&i<n1){

                a[k]=arr1[i];

                i++;

            }

            else if(arr1[i]>arr2[j]&&j<n2){

                a[k]=arr2[j];

                j++;

            }

        }

    }

    

    

}