Implement Merge Sort Algorithm in Java

Exercise:

Write a Java Program to implement Merge Sort Algorithm.

Click Here to View the Solution!
import java.util.Arrays; 

public class MergeSort {
    void merge(int array[], int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;
        int A[] = new int[n1];
        int B[] = new int[n2];
       
        // fill both arrays
        for (int i = 0; i < n1; i++)
            A[i] = array[p + i];
        for (int j = 0; j < n2; j++)
            B[j] = array[q + 1 + j];
      
        //Maintain current index of sub-arrays and main array
        int i, j, k;
        i = 0;
        j = 0;
        k = p;
        while (i < n1 && j < n2) {
            if (A[i] <= B[j]) {
                array[k] = A[i];
                i++;
            } else {
                array[k] = B[j];
                j++;
            }
            k++;
        }
        while (i < n1) {
            array[k] = A[i];
            i++;
            k++;
        }
        while (j < n2) {
            array[k] = B[j];
            j++;
            k++;
        }
    }
  
    //Divide the array into two sub-arrays to sort and merge them
    void mergeSort(int array[], int left, int right) {
        if (left < right) {
          
            // m is the midpoint of array
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }
    public static void main(String args[]) {   

        //created an unsorted array
        int[] array = { -9,5,2,28,90, 9, 1 };
        MergeSort ob = new MergeSort();
       
        //call the method mergeSort()
        ob.mergeSort(array, 0, array.length - 1);
        System.out.println("Sorted Array:");
        System.out.println(Arrays.toString(array));
    }
}
Click Here to View the Output!
Sorted Array:
 [-9, 1, 2, 5, 9, 28, 90]

Click Here to View the Explanation!
  • This program is used to perform the implementation of the merge sort algorithm.
  • Initially, for a given array, two sub-arrays are initialized as L[] and M[].
  • Two for loops are used to iterate between the elements of the array to insert all the left-side elements in L[] and all the right-side elements in M[].
  • Each of the sub-arrays are sorted in ascending order through a while loop and using the condition (L[i] <= M[j]).
  • A mergeSort() method is used to merge the two sub-arrays into a single array[] using a mid-point and the previous merge() method.
  • Finally, in main, an integer array array is initialized as { -9,5,2,28,90, 9, 1 } over which the mergeSort() method is applied that will give the output [-9, 1, 2, 5, 9, 28, 90].
  • The elements can also be sorted in descending order by changing the if statement as (L[i] >= M[j]).

%d bloggers like this: