Merge Sort

What is Merge Sort

Merge sort is a Divide and Conquer algorithm that is based on Recursion. It breaks an array into two halves, sorts these halves and then merges them together to give you a Sorted array.

Dry Run

Code Sample

static void mergeSort(int[] arr, int start, int end){
        if(end - start == 1){ // base condition
            return;
        }
        int mid = (end + start) / 2;
         // Giving the two arrays with their indexes
            mergeSort(arr, 0,mid);
            mergeSort(arr, mid, end);

            // Calling the Merge Function
            merge(arr, start, mid, end);
    }

    static void merge(int[] arr, int start, int mid, int end) {
        // Made of Size equal to the original array
        int[] merge = new int[end - start]; 

        int i = start; // The First Pointer
        int j = mid; // The Second Pointer
        int k = 0; // Index Replacement for the merge array

        // These holds true until one of the index reaches the end of array

        while(i < mid && j < end) { 

            // Comparing the elements and passing the smaller one first
            if (arr[i] < arr[j]) {
                // Pass the smaller value into the new merge array
                merge[k] = arr[i];
                i++;
            } else {
                // Pass the smaller value into the new merge array
                merge[k] = arr[j];
                j++;
            }
            // Increase the index after addition of value
            k++;
        }

        // This triggers when the index of one array runs out of the array
        while(i < mid){
            merge[k] = arr[i];
            i++;
            k++;
        }
        while(j < end){
            merge[k] = arr[j];
            j++;
            k++;
        }

        // Updating the values of merge array into the original array
        for (int l = 0; l < merge.length; l++) {
            arr[start + l] = merge[l];
        }
    }