Merge Sort in Java Explained with Examples (Complete Guide)

 

Merge Sort in Java (Complete Explanation for Beginners to Advanced)

---

 What is Merge Sort? 

Merge Sort is a divide-and-conquer based sorting algorithm that divides an array into smaller subarrays, recursively sorts those subarrays, and then merges them back together in sorted order. Instead of comparing adjacent elements like basic sorting methods, Merge Sort splits the array into halves until each subarray contains only one element. Then it systematically merges them in a sorted manner. Due to its consistent time complexity of O(n log n), Merge Sort is highly efficient and widely used in real-world applications.

---

 Core Concept: Divide and Conquer

Merge Sort works in three steps:

Divide → Split array into two halves
Conquer → Recursively sort both halves
Combine → Merge sorted halves

---

 Real Life Example

Socho tumhare paas 8 exam papers hain random order me.

Instead of sorting all at once:

• Pehle 4 aur 4 me divide karo

• Fir 2 aur 2 me divide karo

• Fir single paper level tak divide karo

Ab combine karte waqt compare karke sorted order me merge karo.

Ye smart sorting approach hai.

---

 How Merge Sort Actually Works

Example Array:

[8, 3, 5, 1]

Step 1: Divide
[8, 3] and [5, 1]

Step 2: Further Divide
[8] [3] [5] [1]

Step 3: Merge Sorted
[3, 8] and [1, 5]

Final Merge →
[1, 3, 5, 8]

---

 Java Implementation

public class MergeSort {

    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];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {

            int mid = left + (right - left) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

    public static void main(String[] args) {

        int[] arr = {8, 3, 5, 1, 9, 6};

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

        for (int num : arr)
            System.out.print(num + " ");
    }
}

---

 Time Complexity

Best Case → O(n log n)
Average Case → O(n log n)
Worst Case → O(n log n)

Ye stable performance deta hai.

---

Space Complexity

O(n)

Kyuki extra temporary arrays use hote hain merge step me.

---

 Why Merge Sort Important for Interviews?

✔ Predictable performance
✔ Stable sorting algorithm
✔ Linked List sorting me useful
✔ Divide and conquer understanding strong karta hai

---

 When to Use Merge Sort?

✔ Large datasets
✔ Stable sorting required
✔ External sorting

---

 Bubble vs Merge Sort Difference

Bubble Sort → O(n²)
Merge Sort → O(n log n)

Large data me difference huge hota hai.

---

Conclusion

Merge Sort ek powerful and efficient sorting algorithm hai jo divide-and-conquer approach par based hai.
Ye beginner ke liye thoda complex ho sakta hai, lekin interviews ke liye must-know topic hai.

Next article me hum Quick Sort (Most Asked Interview Sorting Algorithm) detail me samjhenge.

Agar tumne Merge Sort properly samjha hai, to in sawalon ka answer khud try karo:

1️⃣ Agar array size 16 ho, to Merge Sort maximum kitni levels tak divide karega?
2️⃣ Merge Sort ka time complexity O(n log n) kyu hota hai, O(n²) kyu nahi?
3️⃣ Kya Merge Sort sorted array par bhi same time leta hai?

👇 Apna answer comments me likho ya khud dry run karke check karo.