Implementing the Merge Sort Algorithm in Java

Java Implementation of Merge Sort¶

What is Merge Sort?¶

Merge Sort is an efficient sorting algorithm based on the divide-and-conquer paradigm. Its core idea is to break down a large problem into smaller subproblems, solve the subproblems, and then combine the results. Specifically, it divides the array into two halves, recursively sorts each half, and finally merges the two sorted subarrays into a complete sorted array.

Core Steps of Merge Sort¶

Merge Sort follows the “divide and conquer” principle, consisting of three steps:
1. Divide: Split the unsorted array into two subarrays from the middle until each subarray contains only one element (which is naturally sorted).
2. Conquer: Recursively sort the left and right subarrays.
3. Combine: Merge the two sorted subarrays into a larger sorted array.

Implementing Merge Sort in Java¶

Let’s use a simple integer array as an example to understand how to implement Merge Sort in Java, step by step.

1. Recursive Sorting Method (mergeSort)¶

First, we need a recursive method to handle the divide and conquer steps. The core logic is:
- If the array length is 1 or less, return immediately (it is already sorted).
- Calculate the middle index, recursively sort the left and right subarrays.
- Merge the two sorted subarrays.

import java.util.Arrays;

public class MergeSort {
    // Main merge sort method
    public static void mergeSort(int[] arr) {
        // Base case: array of length <= 1 is already sorted
        if (arr.length <= 1) {
            return;
        }
        // Calculate the middle index to split the array
        int mid = arr.length / 2;
        // Recursively sort the left half
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        mergeSort(left);
        // Recursively sort the right half
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        mergeSort(right);
        // Merge the two sorted subarrays
        merge(arr, left, right);
    }
}

2. Merging Method (merge)¶

The merge step is critical for Merge Sort, as it combines two sorted subarrays into one sorted array. The logic is:
- Use three pointers to traverse the left subarray, right subarray, and the merged result array.
- Compare elements from the left and right subarrays, placing the smaller element into the result array.
- Copy any remaining elements from the unprocessed subarray to the result array.

public class MergeSort {
    // ... mergeSort method omitted for brevity ...

    // Merge two sorted subarrays into the original array
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0; // Pointer for left subarray
        int j = 0; // Pointer for right subarray
        int k = 0; // Pointer for the result array
        // Compare elements from left and right subarrays
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k] = left[i];
                i++;
            } else {
                result[k] = right[j];
                j++;
            }
            k++;
        }
        // Copy remaining elements from the left subarray
        while (i < left.length) {
            result[k] = left[i];
            i++;
            k++;
        }
        // Copy remaining elements from the right subarray
        while (j < right.length) {
            result[k] = right[j];
            j++;
            k++;
        }
    }
}

3. Complete Code and Testing¶

Integrate the above methods into a complete Java program and test it:

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 3, 7, 6, 1, 8};
        System.out.println("Before sorting: " + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("After sorting: " + Arrays.toString(arr));
    }

    // Merge sort main method
    public static void mergeSort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        mergeSort(left);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        mergeSort(right);
        merge(arr, left, right);
    }

    // Merge two sorted subarrays
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k] = left[i];
                i++;
            } else {
                result[k] = right[j];
                j++;
            }
            k++;
        }
        while (i < left.length) {
            result[k] = left[i];
            i++;
            k++;
        }
        while (j < right.length) {
            result[k] = right[j];
            j++;
            k++;
        }
    }
}

Output:

Before sorting: [5, 2, 9, 3, 7, 6, 1, 8]
After sorting: [1, 2, 3, 5, 6, 7, 8, 9]

Algorithm Analysis¶

Time Complexity:
Each merge operation processes all n elements (O(n)), and the recursion depth is log n (number of divisions). Thus, the total time complexity is O(n log n).
Space Complexity:
Requires additional temporary arrays of size n to store merged results, so the space complexity is O(n).
Stability:
Merge Sort is a stable sort (the relative order of equal elements is preserved), as equal elements from the left subarray are prioritized during merging.

Summary¶

Merge Sort efficiently sorts using the divide-and-conquer paradigm with a time complexity of O(n log n), making it suitable for large datasets. Although it requires extra space, its clear logic and ease of understanding make it a classic example for learning divide-and-conquer algorithms. By recursively splitting and merging sorted subarrays, it produces a fully sorted array.