Merge Sort Algorithm in Java

1. Introduction

Merge Sort is a divide-and-conquer sorting algorithm that splits an array into two halves, recursively sorts both halves, and then merges the two sorted halves to produce a single sorted array. It offers a time complexity of O(n log n) making it one of the more efficient sorting algorithms for larger datasets.

2. Implementation Steps

1. If the array has one or zero elements, it is already sorted. Return the array.

2. Otherwise, split the array into two halves.

3. Recursively sort both halves.

4. Merge the two sorted halves to produce a single sorted array.

5. Return the merged and sorted array.

3. Implementation in Java

public class MergeSort {
    // Merge function to merge two sorted halves
    public static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; ++i) {
            L[i] = arr[l + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = arr[m + 1 + j];
        }
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    // Merge Sort function
    public static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }
    // Function to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original array:");
        printArray(arr);
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Output:

Original array:
64 34 25 12 22 11 90
Sorted array:
11 12 22 25 34 64 90

Explanation:

1. The merge function is used to merge two sorted halves of an array.

2. Temporary arrays L and R are created to hold the two halves to be merged.

3. The mergeSort function is a recursive function that sorts the input array.

4. If the current segment of the array has more than one element, it splits the segment into two, sorts both recursively using mergeSort, and then merges them using the merge function.

5. The main function initializes an array, prints its original contents, sorts it using the mergeSort function, and then prints the sorted array.