1. Introduction

Merge Sort is a well-known, efficient, and stable sorting algorithm based on the Divide and Conquer paradigm.

Instead of sorting the array directly, it divides the array into smaller subarrays, sorts them individually, and then merges them into a fully sorted array.

2. Key Properties of Merge Sort

Property	Description
Time Complexity	O(n log n) for all cases (best, average, worst)
Space Complexity	O(n) – uses temporary arrays during merge
Stable	Yes, it maintains the relative order of equal elements
Recursive	Yes (most commonly implemented recursively)
In-Place	No, uses additional memory

3. Merge Sort Conceptual Steps

Given an array:

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

The process works in the following two main phases:

3.1 Divide Phase

Keep dividing the array into two halves recursively until each subarray has only one element.

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

3.2 Conquer (Merge Phase)

Merge the subarrays while sorting them during the merge.

[38] + [27] → [27, 38]
[43] + [3] → [3, 43]
[9] + [82] → [9, 82]
[10] remains as it is

Then:
[27, 38] + [3, 43] → [3, 27, 38, 43]
[9, 82] + [10] → [9, 10, 82]

Final:
[3, 27, 38, 43] + [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

4. Java Implementation of Merge Sort

public class MergeSort {

    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};

        System.out.println("Original Array:");
        printArray(array);

        mergeSort(array, 0, array.length - 1);

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

    // Recursive mergeSort function
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // Find the middle point
            int middle = left + (right - left) / 2;

            // Recursively sort the left half
            mergeSort(arr, left, middle);

            // Recursively sort the right half
            mergeSort(arr, middle + 1, right);

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

    // Merges two subarrays of arr[]
    public static void merge(int[] arr, int left, int middle, int right) {
        // Find sizes of two subarrays to be merged
        int n1 = middle - left + 1;
        int n2 = right - middle;

        // Create temporary arrays
        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data to temp arrays
        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[middle + 1 + j];

        // Merge the temp arrays

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarray
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }

        // Copy remaining elements of L[]
        while (i < n1) {
            arr[k++] = L[i++];
        }

        // Copy remaining elements of R[]
        while (j < n2) {
            arr[k++] = R[j++];
        }
    }

    // Utility function to print the array
    public static void printArray(int[] arr) {
        for (int value : arr)
            System.out.print(value + " ");
        System.out.println();
    }
}

5. Advantages of Merge Sort

• Consistent Performance: O(n log n) for all inputs.
• Stable: Keeps order of equal elements.
• Works well with Linked Lists: Since insertion and merge are efficient.
• Predictable Behavior: Good for real-time systems.

6. Disadvantages

• Extra Space Needed: Requires temporary arrays.
• Not In-place: Unlike Quick Sort, it uses O(n) auxiliary space.
• Slower on Small Datasets: Insertion sort can be better for tiny arrays.