Merge Sort: The gateway to Divide and Conquer

Himanshu Nailwal

·

Follow

2 min read

·

Jul 4, 2021

--

Listen

Share

public class MergeSort {
    // mergesort -> to divide the array
    // conquer -> to compare the element and combine them


    public void merge(int arr[], int left, int mid, int right){
            //size of two temporary sub arrays
            int n1 = mid - left+1;
            int n2 = right - mid;

            // Created two temporary sub arrays
            int[] L = new int[n1];
            int[] R = new int[n2];

            //Let's copy the original content of array into temporary arrays
            for(int i = 0; i < n1; i++)
                L[i] = arr[left + i];


            for(int j = 0; j < n2; j++)
                R[j] = arr[mid + 1 + j];


            //Index for the first element of subarray
            int i=0, j=0;

            //index for the original array
            int k = left;

            // Merge logic
            while(i<n1 && j<n2){
                if(L[i] <= R[j]){
                    arr[k] = L[i];
                    i++;
                }
                else{
                    arr[k] = R[j];
                    j++;
                }
                k++;
            }
            //printArray(arr);

        //System.out.println("i: "+ i + " j: "+ j);
            //If left subarray elements are left
            while(i < n1){
                arr[k] = L[i];
                i++;
                k++;

            }

            // If right subarray elements are left
            while(j < n2){
                arr[k] = R[j];
                j++;
                k++;
            }
    }

    public void sort(int arr[], int left, int right){
        if(right > left){
            int mid = left + ((right - left)/2);

            sort(arr, left, mid);
            sort(arr, mid+1, right);

            //Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    public void printArray(int[] arr){
        for(int i=0;i < arr.length;i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void main(String[] args) {
        MergeSort ms = new MergeSort();
        int arr[] = { 12, 11, 13, 5, 6, 7 };
        System.out.println("Given array is: ");
        ms.printArray(arr);

        ms.sort(arr, 0, arr.length-1);

        System.out.println("Sorted array is: ");
        ms.printArray(arr);
    }

}