[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;
     }