Java program to implement merge sort algorithm

‮//:sptth‬www.theitroad.com

Here is an example Java program that implements the Merge Sort algorithm:

import java.util.Arrays;

public class MergeSortExample {
    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        System.out.println("Original array: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

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

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] leftArr = new int[mid - left + 1];
        int[] rightArr = new int[right - mid];

        for (int i = 0; i < leftArr.length; i++) {
            leftArr[i] = arr[left + i];
        }

        for (int i = 0; i < rightArr.length; i++) {
            rightArr[i] = arr[mid + 1 + i];
        }

        int i = 0;
        int j = 0;
        int k = left;

        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        while (i < leftArr.length) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }

        while (j < rightArr.length) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }
}

In this program, we first create an array of integers arr and initialize it with the values {5, 4, 3, 2, 1}. We then call the mergeSort() method with the array and the indices of the first and last elements of the array as arguments.

The mergeSort() method implements the Merge Sort algorithm recursively. It first checks if the indices of the first and last elements of the array are in the correct order. If they are not, it calculates the index of the middle element and calls mergeSort() recursively on the left and right halves of the array. Finally, it calls the merge() method to merge the sorted halves of the array.

The merge() method takes three arguments: the array to be sorted and the indices of the first and last elements of each half of the array. It creates two new arrays to hold the left and right halves of the array, copies the appropriate elements from the original array into these new arrays, and then iteratively compares the elements in the left and right arrays and places them in the correct order in the original array.

The sorted array is then printed to the console using the Arrays.toString() method.