Overview

Merge Sort is a divide-and-conquer algorithm that sorts an array by recursively dividing it into two halves,
sorting those halves, and then merging them back together. This algorithm has a time complexity of O(n log n)
and is known for its efficiency in handling large datasets.

Java Implementation

public class MergeSort {

    // Main function that sorts array[left...right] using merge()
    public void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        int[] tempArray = new int[array.length];
        mergeSort(array, 0, array.length - 1, tempArray);
    }

    // Recursive function to sort the array
    private void mergeSort(int[] array, int left, int right, int[] tempArray) {
        if (left < right) {
            int mid = (left + right) / 2;

            // Sort the first half
            mergeSort(array, left, mid, tempArray);
            // Sort the second half
            mergeSort(array, mid + 1, right, tempArray);
            // Merge the sorted halves
            merge(array, left, mid, right, tempArray);
        }
    }

    // Merges two subarrays of array[]
    private void merge(int[] array, int left, int mid, int right, int[] tempArray) {
        // Copy data to temp array
        for (int i = left; i <= right; i++) {
            tempArray[i] = array[i];
        }

        int i = left;      // Starting index for left subarray
        int j = mid + 1;   // Starting index for right subarray
        int k = left;      // Starting index to be sorted

        // Merge the temp arrays back into array[left...right]
        while (i <= mid && j <= right) {
            if (tempArray[i] <= tempArray[j]) {
                array[k] = tempArray[i];
                i++;
            } else {
                array[k] = tempArray[j];
                j++;
            }
            k++;
        }

        // Copy the remaining elements of left subarray, if any
        while (i <= mid) {
            array[k] = tempArray[i];
            i++;
            k++;
        }

        // No need to copy the right subarray as they are already in place
    }

    // Main method to test the sorting algorithm
    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        
        System.out.println("Original Array:");
        printArray(array);
        
        mergeSort.sort(array);
        
        System.out.println("Sorted Array:");
        printArray(array);
    }

    // Utility method to print the array
    private static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Program Structure

The MergeSort class contains methods to perform the merge sort operation.
The main components of the program are:

• sort(int[] array): This is the main method that initializes the sorting process.
• mergeSort(int[] array, int left, int right, int[] tempArray): This recursive method divides the array into halves.
• merge(int[] array, int left, int mid, int right, int[] tempArray): This method merges two sorted halves back into a single sorted array.
• printArray(int[] array): A utility method to print the contents of the array.

How to Run the Program

To run the program, copy the code into a file named MergeSort.java and compile it using a Java compiler:

javac MergeSort.java
java MergeSort

The output will display the original and sorted arrays.