Java Program for Merge Sort with Example and Explanation

A Java program for merge sort uses a mergeSort method to split the array and a merge method to combine sorted parts; for example, mergeSort(arr, 0, arr.length - 1) sorts the array in place.

Examples

Input[5, 3, 8, 4, 2]

Output[2, 3, 4, 5, 8]

Input[1, 2, 3, 4, 5]

Output[1, 2, 3, 4, 5]

Input[]

Output[]

How to Think About It

To sort an array using merge sort, first split the array into two halves repeatedly until each part has one element. Then, merge these small parts back together in sorted order by comparing elements from each half. This process uses divide and conquer to sort efficiently.

Algorithm

1

Check if the array has more than one element; if not, return.

2

Find the middle index to split the array into two halves.

3

Recursively apply merge sort on the left half.

4

Recursively apply merge sort on the right half.

5

Merge the two sorted halves into one sorted array.

Code

java

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) L[i] = arr[left + i];
        for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }

        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        mergeSort(arr, 0, arr.length - 1);
        for (int num : arr) System.out.print(num + " ");
    }
}

Output

2 3 4 5 8 

Dry Run

Let's trace sorting the array [5, 3, 8, 4, 2] through the merge sort code.

1

Split array

Split [5, 3, 8, 4, 2] into [5, 3, 8] and [4, 2]

2

Split left half

Split [5, 3, 8] into [5, 3] and [8]

3

Split left-left half

Split [5, 3] into [5] and [3]

4

Merge [5] and [3]

Compare 5 and 3, merge into [3, 5]

5

Merge [3, 5] and [8]

Merge sorted arrays [3, 5] and [8] into [3, 5, 8]

6

Split right half

Split [4, 2] into [4] and [2]

7

Merge [4] and [2]

Compare 4 and 2, merge into [2, 4]

8

Merge [3, 5, 8] and [2, 4]

Merge sorted arrays into [2, 3, 4, 5, 8]

Step	Array State
Initial	[5, 3, 8, 4, 2]
Split	[5, 3, 8] and [4, 2]
Split	[5, 3] and [8]
Split	[5] and [3]
Merge	[3, 5]
Merge	[3, 5, 8]
Split	[4] and [2]
Merge	[2, 4]
Merge	[2, 3, 4, 5, 8]

Why This Works

Step 1: Divide the array

The code uses mergeSort to split the array into smaller parts until each part has one element, which is naturally sorted.

Step 2: Merge sorted parts

The merge method combines two sorted arrays by comparing elements and placing the smaller one first, building a bigger sorted array.

Step 3: Recursive sorting

By recursively splitting and merging, the entire array becomes sorted efficiently without sorting the whole array at once.

Alternative Approaches

Iterative Merge Sort

java

public class IterativeMergeSort {
    public static void mergeSort(int[] arr) {
        int n = arr.length;
        for (int currSize = 1; currSize < n; currSize *= 2) {
            for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) {
                int mid = Math.min(leftStart + currSize - 1, n - 1);
                int rightEnd = Math.min(leftStart + 2 * currSize - 1, n - 1);
                merge(arr, leftStart, mid, rightEnd);
            }
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) L[i] = arr[left + i];
        for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) arr[k++] = L[i++];
            else arr[k++] = R[j++];
        }
        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        mergeSort(arr);
        for (int num : arr) System.out.print(num + " ");
    }
}

This approach avoids recursion but is more complex to understand; it uses loops to merge subarrays of increasing size.

Using Java's Arrays.sort()

java

import java.util.Arrays;
public class BuiltInSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        Arrays.sort(arr);
        for (int num : arr) System.out.print(num + " ");
    }
}

This uses Java's built-in optimized sort, which is simpler but does not teach the merge sort algorithm.

Complexity: O(n log n) time, O(n) space

Time Complexity

Merge sort divides the array into halves recursively (log n splits) and merges all elements (n) at each level, resulting in O(n log n) time.

Space Complexity

Extra arrays are used during merging to hold temporary values, so space complexity is O(n).

Which Approach is Fastest?

Recursive merge sort is clear and efficient; iterative merge sort avoids recursion overhead but is more complex; built-in sorts may be faster but hide the algorithm.

Approach	Time	Space	Best For
Recursive Merge Sort	O(n log n)	O(n)	Learning and general sorting
Iterative Merge Sort	O(n log n)	O(n)	Avoiding recursion overhead
Java Arrays.sort()	O(n log n)	O(log n)	Production use with optimized native code