Google News
logo
Java Program to Implement Merge Sort

What is a Merge Sort in Java?

Merge sort algorithm is used to sort a group of elements. It is a general purpose comparison based algorithm. Merge sort is based on the principe of divide-and-conquer approach that was invented by John von Neumann in 1945.

In the following examples of Java program to implement Merge Sort :
Program :
public class MergeSort {
    
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 3};
        System.out.println("Before sorting:");
        printArray(arr);
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("After sorting:");
        printArray(arr);
    }

    public static void mergeSort(int[] arr, int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merge(arr, start, mid, end);
        }
    }

    public static void merge(int[] arr, int start, int mid, int end) {
        int n1 = mid - start + 1;
        int n2 = end - mid;
        int[] left = new int[n1];
        int[] right = new int[n2];
        for (int i = 0; i < n1; i++) {
            left[i] = arr[start + i];
        }
        for (int i = 0; i < n2; i++) {
            right[i] = arr[mid + 1 + i];
        }
        int i = 0, j = 0, k = start;
        while (i < n1 && j < n2) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
        while (i < n1) {
            arr[k++] = left[i++];
        }
        while (j < n2) {
            arr[k++] = right[j++];
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
Output :
Before sorting:5 2 8 1 3 
After sorting:
1 2 3 5 8 
In this program, we declare an integer array arr and initialize it with the values 5, 2, 8, 1, and 3. We then print the array before sorting using the printArray method.

We then call the mergeSort method and pass the array, the start index (0), and the end index (length - 1) as arguments. This method recursively divides the array into two halves until each half contains only one element, then merges the two halves into a sorted array using the merge method.

The merge method takes the array, the start index of the first half, the end index of the first half (which is also the mid index of the original array), and the end index of the second half as arguments. It first creates two new arrays to store the elements of each half, then copies the elements from the original array into the two new arrays. It then merges the two arrays into a sorted array by comparing the first elements of each array, and copying the smaller element into the original array. It repeats this process until all elements have been copied into the original array.

Finally, we print the array after sorting using the printArray method.