Merge Sort Recursive

public class Merge {
    public int [] data;
    private int [] helper;
   
   
    public Merge(int[] a){
        data=a;
        this.helper = new int[a.length];
    }
   
    public void splitAndMerge(int begin, int end){
       
        if(begin<end){
            int middle = (begin+end)/2;
            splitAndMerge(begin, middle);
            splitAndMerge(middle+1, end);
            MergeSort(begin, middle, end);
        }
    }
   
    public void MergeSort(int begin, int middle, int end){
         for(int i=begin;i<=end;i++){
             helper[i]=data[i];
         }
   
         int x=begin;
         int y=middle+1;
         int z=begin;
       
         while(x<=middle&&y<=end){
             if(helper[x]<=helper[y]){
                    data[z]=helper[x];
                    x++;
                    z++;
             }
             else{
                     data[z]=helper[y];
                     y++;
                     z++;
             }
         }
       
         //Copy the rest of left to the array
         while(x<=middle){
             data[z]=helper[x];
             z++;
             x++;
         }
    }
}

[Introduction to Algorithms] Merge Sort Example

Book - [Introduction to Algorithms]
Page 31

Divide-and-conquer approach: they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem.

Coded in Java
Merge sort example
O(n)

public static void main(String[] args) {
        int [] data={99,7,3,4,6,23,34,5,2,100};
        int [] newdata = MergeSort.mergeSort(data, 1, 4, 8);
        for(int i=0;i<newdata.length;i++){
            System.out.print(newdata[i]+" ");
        }
    }
public static int[] mergeSort(int[] data, 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];
        int index = p ;



//Sort Left
        for(int i=0;i<L.length;i++){
            L[i]=data[p];
            p++;
        }
        Arrays.sort(L);
        L[n1]=Integer.MAX_VALUE;

//Sort Right       
        for(int i=0;i<R.length;i++){
            R[i]=data[q+1];
            q++;
        }
        Arrays.sort(R);
        R[n2]=Integer.MAX_VALUE;
       
//Here comes the merge of left and right
         for(int i=0, j=0;index<r+1;){
            if(L[i]>=R[j]){
                data[index++]=R[j++];
            }
            else if(L[i]<R[j]){
                data[index++]=L[i++];
            }
        }
        return data;
     }