Merge Sort Using Divide and Conquer

Algorithm

Merge_Sort(A,p,r)
{
       if(p<r)
         q=[(p+r)/2]
         Merge_Sort(A,p,q)
         Merge_Sort(A,q+1,r)
         Merge(A,p,q,r)
}
Merge(A,p,q,r){
n1=q-p+1
n2=r-q
Let L[1...n1+1] and R[1....n2+1] be two new arrays
for(i=1 to n1)
     L[i]=A[i]
for(j=1 to n2)
     R[j]=A[j]
L[n1+1]=infinity(large number)
R[n2+1]=infinity(large number)
i=1,j=1
for(k=p to r)
     if(L[i]<R[j])
       A[k]=L[i]
       i=i+1
     else
        A[k]=R[j]
         j=j+1

Code

class mergesort{
    public static void main(String args[]){
        int arr[]={3,2,1,6,9};
        merge_sort(arr,0,arr.length-1);
        for(int i:arr){
            System.out.print(i+" ");
        }
    }
    static int[] merge_sort(int arr[],int p,int r){
        if(p<r){
            int q=((p+r)/2);
            merge_sort(arr, p, q);
            merge_sort(arr, q+1, r);
            merge(arr,p,q,r);
        }
        return arr;
    }
  static int[] merge(int arr[],int p,int q,int r){
    int n1=q-p+1;
    int n2=r-q;
    int L[]=new int[n1+1];
    int R[]=new int[n2+1];

    for(int i=0;i<n1;i++){
        L[i]=arr[p+i];

    }
    for(int j=0;j<n2;j++){
        R[j]=arr[q+j+1];
    }
    L[n1]=Integer.MAX_VALUE;
    R[n2]=Integer.MAX_VALUE;
    int i=0,j=0;
    for(int k=p;k<=r;k++){
        if(L[i]<R[j])
        {
            arr[k]=L[i];
            i++;
        }
        else{
            arr[k]=R[j];
            j++;
        }
    }
    return  arr;
   }
}

Output

1 2 3 6 9