Merge Sort in Java

intermediate· Arrays · Sorting

Problem

Merge sort is a divide-and-conquer algorithm: it keeps halving the array until each piece holds one element, then merges neighbouring pieces back together in sorted order.

Given an array of integers, sort it in ascending order using merge sort.

Input

[29, 4, 17, 8, 35, 12, 1]

Output

[1, 4, 8, 12, 17, 29, 35]

Java Program

Java

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {29, 4, 17, 8, 35, 12, 1};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return; // zero or one element is already sorted
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    static void merge(int[] arr, int left, int mid, int right) {
        int[] leftPart = Arrays.copyOfRange(arr, left, mid + 1);
        int[] rightPart = Arrays.copyOfRange(arr, mid + 1, right + 1);

        int i = 0, j = 0, k = left;
        while (i < leftPart.length && j < rightPart.length) {
            // <= keeps equal values in their original order, which makes the sort stable
            arr[k++] = leftPart[i] <= rightPart[j] ? leftPart[i++] : rightPart[j++];
        }
        while (i < leftPart.length) arr[k++] = leftPart[i++];   // copy whatever is left over
        while (j < rightPart.length) arr[k++] = rightPart[j++];
    }
}

▶ Run Code

Output

[1, 4, 8, 12, 17, 29, 35]

Core Logic

Sorting is easy for tiny pieces and merging two sorted lists is cheap, so the array is split until every piece is trivially sorted, then stitched back together pair by pair.

How It Works

1mergeSort(arr, left, right) returns immediately when left >= right, since a range of zero or one element is already sorted.
2Otherwise it finds mid, sorts left..mid and mid+1..right recursively, then calls merge.
3merge copies both halves into temporary arrays and repeatedly writes the smaller front value back into arr.
4When one half runs out, the remaining values of the other half are copied over unchanged.

The sorted halves [4, 29] and [8, 17] merge by comparing their fronts: 4 is taken first, then 8 and 17 (both smaller than 29), and finally 29, giving [4, 8, 17, 29].

💡

Key Point: Using <= in the merge comparison takes the left value first when two are equal, which keeps equal elements in their original order — that's what makes merge sort a stable sort.

Complexity

Time Complexity: O(n log n)Space Complexity: O(n)

Why: The array is halved about log n times and every level of merging touches all n elements, while each merge needs temporary copies of the halves.

Key Concepts

recursiondivide and conquermerging sorted arraysArrays.copyOfRange()

Approach 2: Bottom-Up (Iterative)

Java

import java.util.Arrays;

public class MergeSortBottomUp {
    public static void main(String[] args) {
        int[] arr = {29, 4, 17, 8, 35, 12, 1};
        int n = arr.length;

        for (int width = 1; width < n; width *= 2) {          // run length doubles each round: 1, 2, 4, ...
            for (int left = 0; left < n - width; left += 2 * width) {
                int mid = left + width - 1;
                int right = Math.min(left + 2 * width - 1, n - 1); // last run may be shorter
                merge(arr, left, mid, right);
            }
        }

        System.out.println(Arrays.toString(arr));
    }

    static void merge(int[] arr, int left, int mid, int right) {
        int[] leftPart = Arrays.copyOfRange(arr, left, mid + 1);
        int[] rightPart = Arrays.copyOfRange(arr, mid + 1, right + 1);

        int i = 0, j = 0, k = left;
        while (i < leftPart.length && j < rightPart.length) {
            arr[k++] = leftPart[i] <= rightPart[j] ? leftPart[i++] : rightPart[j++];
        }
        while (i < leftPart.length) arr[k++] = leftPart[i++];
        while (j < rightPart.length) arr[k++] = rightPart[j++];
    }
}

▶ Run Code

Output

[1, 4, 8, 12, 17, 29, 35]

Core Logic

The recursion can be dropped entirely by starting from the bottom: treat every element as a sorted run of length 1, merge neighbouring runs into runs of 2, then 4, and so on.

How It Works

1The outer loop doubles width each round: 1, 2, 4, …
2The inner loop steps through the array in blocks of 2 * width, merging the two runs in each block.
3Math.min(left + 2 * width - 1, n - 1) trims the last block so a shorter final run is handled correctly.
4The same merge helper as the recursive version does the actual combining.

With width 1 the pairs (29, 4), (17, 8), (35, 12) become sorted pairs; with width 2 those pairs merge into runs of four, and with width 4 the whole array is merged.

💡

Key Point: Avoiding recursion removes the call stack overhead and any risk of deep recursion, while keeping the same O(n log n) running time and stability.

Complexity

Time Complexity: O(n log n)Space Complexity: O(n)

Why: There are about log n doubling rounds, each merging all n elements, and merges still copy halves into temporary arrays.

Key Concepts

iterative mergingrun width doublingno recursion

Interview Questions

Why does merge sort need extra memory?

Merging two sorted halves needs somewhere to hold one or both halves while the result is written back, which costs O(n) extra space.

Where is merge sort used in Java?

Arrays.sort on object arrays and Collections.sort use TimSort, a merge-sort variant, because it's stable.

← Previous

Linear Search

Merge Two Arrays

Learn the Concept

📘 Passing Arrays to Methods

Related Programs

Arraysintermediate

Quick Sort

Recursionbeginner

Array Sum Using Recursion

Numbersintermediate

Calculate Power Using Recursion

Recursionbeginner

Check Palindrome Using Recursion

Recursionbeginner

Factorial