Merge Sort in Java

 

Merge Sort

Merge Sort is an efficient, stable, and comparison-based sorting algorithm. It follows the divide-and-conquer paradigm by recursively dividing the unsorted list into two halves, sorting each half, and then merging the sorted halves to produce the final sorted list.

What is Merge Sort?

Merge Sort is a sorting algorithm that works by dividing the input array into two halves, recursively sorting each half, and then merging the sorted halves to produce the final sorted array.

Example:

• Unsorted List: [38, 27, 43, 3, 9, 82, 10]

• Sorted List: [3, 9, 10, 27, 38, 43, 82]

Solution:

Now let’s see how to implement Merge Sort in Java.

 import java.util.Arrays;

public class MergeSort {

    // Function to merge two subarrays

    private static void merge(int[] arr, int left, int mid, int right) {

        int n1 = mid - left + 1;

        int n2 = right - mid;

        int[] leftArr = new int[n1];

        int[] rightArr = new int[n2];

        // Copy data to temporary arrays

        for (int i = 0; i < n1; ++i)

            leftArr[i] = arr[left + i];

        for (int j = 0; j < n2; ++j)

            rightArr[j] = arr[mid + 1 + j];

        int i = 0, j = 0;

        int k = left;

        // Merge the temporary arrays

        while (i < n1 && j < n2) {

            if (leftArr[i] <= rightArr[j]) {

                arr[k] = leftArr[i];

                i++;

            } else {

                arr[k] = rightArr[j];

                j++;

            }

            k++;

        }

        // Copy remaining elements of leftArr[], if any

        while (i < n1) {

            arr[k] = leftArr[i];

            i++;

            k++;

        }

        // Copy remaining elements of rightArr[], if any

        while (j < n2) {

            arr[k] = rightArr[j];

            j++;

            k++;

        }

    }

    // Function to implement Merge Sort

    private static void mergeSort(int[] arr, int left, int right) {

        if (left < right) {

            int mid = (left + right) / 2;

            // Recursively sort first and second halves

            mergeSort(arr, left, mid);

            mergeSort(arr, mid + 1, right);

            // Merge the sorted halves

            merge(arr, left, mid, right);

        }

    }

    public static void main(String[] args) {

        int[] arr = {38, 27, 43, 3, 9, 82, 10};

        System.out.println("Unsorted array: " + Arrays.toString(arr));

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("Sorted array: " + Arrays.toString(arr));

    }

}

Explanation of Code:

Each code version defines a mergeSort function to sort an array using the Merge Sort algorithm.

• Divide: Recursively split the array into two halves until each subarray contains a single element.

• Conquer: Merge the sorted halves to produce

**  Please do subscribe my blog for future updates and share with your friends, if you find this informative **