MERGE SORT IN JAVA

Explanation of Merge Sort

Merge Sort is a sorting algorithm that follows the divide and conquer principle. Here’s a simple breakdown of how it works:

1. Divide: Split the array into two halves.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves into a single sorted array.

Steps of Merge Sort

1. If the array is of length 0 or 1, it is already sorted.
2. Otherwise, divide the array into two halves.
3. Recursively sort each half.
4. Merge the two sorted halves into one sorted array.

Example in Java

Here’s a simple example of how to implement Merge Sort in Java.

public class MergeSortExample {
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        System.out.println("Given Array:");
        printArray(array);

        MergeSortExample ob = new MergeSortExample();
        ob.sort(array, 0, array.length - 1);

        System.out.println("\nSorted array:");
        printArray(array);
    }

    void sort(int[] array, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;

            sort(array, left, middle);
            sort(array, middle + 1, right);

            merge(array, left, middle, right);
        }
    }

    void merge(int[] array, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; ++i) {
            leftArray[i] = array[left + i];
        }
        for (int j = 0; j < n2; ++j) {
            rightArray[j] = array[middle + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            array[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < n2) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }

    static void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

.