Back to DSA Course

Merge Sort is one of the most popular and widely used sorting algorithms. It consistently outperforms Bubble Sort, Selection Sort, and Insertion Sort for large inputs because its time complexity is O(n log n) in all cases — best, average, and worst — compared to O(n²) for the simpler sorts.

Algorithm: Divide and Conquer

• Divide the unsorted list into n sublists, each containing one element (a single element is by definition sorted).
• Repeatedly merge adjacent pairs of sublists into sorted lists of double the size until there is only one list remaining.

For example:

int[] num = { 90, 24, 46, 35, 32 };

Divide phase:

90, 24, 46, 35, 32
90, 24        |    46, 35, 32
90 | 24       |    46   |   35, 32
                            35 | 32

Each sub-array is now a single element (trivially sorted).

Merge phase — merge adjacent sorted sub-arrays in order:

[24, 90]          [35, 46]    [32]       ← merge 90+24, merge 35+46, 32 alone
[24, 90]     [32, 35, 46]                ← merge [35,46] + [32]
[24, 32, 35, 46, 90]                    ← final merge

Let's start coding for merge sort:

package com.praveen.sort;

public class MergeSort {

    public static void main(String[] args) {
        int[] num = { 90, 24, 46, 35, 32 };
        mergeSort(num, num.length);
        for (int i : num) {
            System.out.print(i + " ");
        }
    }

    public static void mergeSort(int[] a, int n) {
        if (n < 2) {
            return;  // base case: single element is already sorted
        }
        int mid = n / 2;
        int[] l = new int[mid];
        int[] r = new int[n - mid];

        for (int i = 0; i < mid; i++) {
            l[i] = a[i];
        }
        for (int i = mid; i < n; i++) {
            r[i - mid] = a[i];
        }
        mergeSort(l, mid);
        mergeSort(r, n - mid);

        merge(a, l, r, mid, n - mid);
    }

    public static void merge(int[] a, int[] l, int[] r, int left, int right) {
        int i = 0, j = 0, k = 0;
        while (i < left && j < right) {
            if (l[i] <= r[j]) {
                a[k++] = l[i++];
            } else {
                a[k++] = r[j++];
            }
        }
        while (i < left) {
            a[k++] = l[i++];
        }
        while (j < right) {
            a[k++] = r[j++];
        }
    }
}

Output

24 32 35 46 90

Complexity

Case     | Time       | Space
---------|------------|------
Best     | O(n log n) | O(n)
Average  | O(n log n) | O(n)
Worst    | O(n log n) | O(n)

Merge sort's O(n) space comes from the temporary sub-arrays (l and r) created at each level of recursion. This is its main disadvantage compared to in-place sorts like Quick Sort. However, its guaranteed O(n log n) worst case makes it preferable over Quick Sort when worst-case performance is critical.

Merge sort is also a stable sort — elements with equal values appear in the same relative order in the sorted output as they did in the input. This matters when sorting objects by a secondary key while preserving a primary sort order.