Merge Sort Algorithm

What is Merge Sort?

Merge Sort is a powerful, efficient, and stable sorting algorithm that uses the divide and conquer paradigm. It is especially effective for large datasets and is often preferred when predictable performance and stability are required.

How It Works

Merge Sort follows three key steps:

1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the sorted halves back together.

This process continues recursively until the array is broken down into subarrays of size 1 (which are inherently sorted), and then merged step-by-step into a sorted array.

Why Use Merge Sort?

• ✅ Performance: Always O(n log n), regardless of input order.
• ✅ Stable: Equal elements maintain original order.
• ✅ Predictable: Unlike Quick Sort, performance doesn’t degrade on certain inputs.

Time and Space Complexity

• Space Complexity: O(n), due to temporary arrays used for merging.

Code Example

public class MergeSortExample {

    public static void mergeSort(int[] array) {
        if (array.length < 2) return;

        int mid = array.length / 2;
        int[] left = new int[mid];
        int[] right = new int[array.length - mid];

        // Split array into left and right halves
        for (int i = 0; i < mid; i++) {
            left[i] = array[i];
        }
        for (int i = mid; i < array.length; i++) {
            right[i - mid] = array[i];
        }

        // Recursive sort
        mergeSort(left);
        mergeSort(right);

        // Merge the sorted halves
        merge(array, left, right);
    }

    public static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        // Merge elements into original array
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                array[k++] = left[i++];
            } else {
                array[k++] = right[j++];
            }
        }

        // Copy remaining elements
        while (i < left.length) {
            array[k++] = left[i++];
        }
        while (j < right.length) {
            array[k++] = right[j++];
        }
    }

    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Original array:");
        printArray(arr);

        mergeSort(arr);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Output

Original array:
38 27 43 3 9 82 10 
Sorted array:
3 9 10 27 38 43 82 

Merge Sort – Visual Explanation (Step-by-Step)

Let’s walk through sorting the array:
[38, 27, 43, 3, 9, 82, 10]

Step 1: Divide

We recursively divide the array:

[38, 27, 43, 3, 9, 82, 10]
→ [38, 27, 43] and [3, 9, 82, 10]
→ [38], [27, 43] and [3, 9], [82, 10]
→ [38], [27], [43], [3], [9], [82], [10]

Step 2: Conquer (Sort each half)

Start merging sorted individual elements:

[27], [43] → [27, 43]
[27, 43], [38] → [27, 38, 43]
[3], [9] → [3, 9]
[82], [10] → [10, 82]
[3, 9], [10, 82] → [3, 9, 10, 82]

Step 3: Combine

Merge the two major sorted halves:

[27, 38, 43], [3, 9, 10, 82]
→ [3, 9, 10, 27, 38, 43, 82]

Final Sorted Array

[3, 9, 10, 27, 38, 43, 82]

Summary

• Merge Sort is reliable and efficient, especially for large datasets.
• It always performs in O(n log n) time and maintains stability.
• While it uses more memory than in-place algorithms like Quick Sort, it is preferred when consistency and stability are important.