LogoKode$word
Merge Sort Algorithm Explained | Java Implementation, Intuition & Complexity
Merge Sort Algorithm Explained | Java Implementation, Intuition & Complexity

Merge Sort Algorithm Explained | Java Implementation, Intuition & Complexity

Learn Merge Sort with step-by-step explanation, recursion, iterative approach, Java code, and complexity analysis. Perfect for coding interviews.

8 views
0
0
Github icon
Github icon
Listen to articleAudio version

Introduction

Sorting is one of the most fundamental operations in computer science, and Merge Sort is among the most efficient and widely used sorting algorithms.

It follows the Divide and Conquer approach, making it highly scalable and predictable even for large datasets.

In this article, we will cover:

  1. Intuition behind Merge Sort
  2. Step-by-step breakdown
  3. Multiple approaches
  4. Java implementation with comments
  5. Time & space complexity analysis

🔗 Problem Link

GeeksforGeeks: Merge Sort

Problem Statement

Given an array arr[] with starting index l and ending index r, sort the array using the Merge Sort algorithm.

Examples

Example 1

Input:

arr = [4, 1, 3, 9, 7]

Output:

[1, 3, 4, 7, 9]

Example 2

Input:

arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Output:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Key Insight

Merge Sort works by:

Divide → Conquer → Combine
  1. Divide the array into two halves
  2. Recursively sort each half
  3. Merge both sorted halves

Intuition (Visual Understanding)

For:

[4, 1, 3, 9, 7]

Step 1: Divide

[4, 1, 3] [9, 7]
[4, 1] [3] [9] [7]
[4] [1]

Step 2: Merge

[4] [1] → [1, 4]
[1, 4] [3] → [1, 3, 4]
[9] [7] → [7, 9]

Step 3: Final Merge

[1, 3, 4] + [7, 9] → [1, 3, 4, 7, 9]

Approach 1: Recursive Merge Sort (Top-Down)

Idea

  1. Keep dividing until single elements remain
  2. Merge sorted subarrays

Java Code

class Solution {

// Function to merge two sorted halves
void merge(int[] arr, int l, int mid, int h) {

// Temporary array to store merged result
int[] temp = new int[h - l + 1];

int i = l; // pointer for left half
int j = mid + 1; // pointer for right half
int k = 0; // pointer for temp array

// Compare elements from both halves
while (i <= mid && j <= h) {

if (arr[i] <= arr[j]) {
temp[k] = arr[i];
i++;
} else {
temp[k] = arr[j];
j++;
}
k++;
}

// Copy remaining elements from left half
while (i <= mid) {
temp[k] = arr[i];
i++;
k++;
}

// Copy remaining elements from right half
while (j <= h) {
temp[k] = arr[j];
j++;
k++;
}

// Copy sorted elements back to original array
for (int m = 0; m < temp.length; m++) {
arr[l + m] = temp[m];
}
}

// Recursive merge sort function
void mergeSort(int arr[], int l, int h) {

// Base case: single element
if (l >= h) return;

int mid = l + (h - l) / 2;

// Sort left half
mergeSort(arr, l, mid);

// Sort right half
mergeSort(arr, mid + 1, h);

// Merge both halves
merge(arr, l, mid, h);
}
}

Approach 2: Iterative Merge Sort (Bottom-Up)

Idea

  1. Start with subarrays of size 1
  2. Merge pairs
  3. Increase size gradually

Code

class Solution {
void merge(int[] arr, int l, int mid, int h) {
int[] temp = new int[h - l + 1];
int i = l, j = mid + 1, k = 0;

while (i <= mid && j <= h) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}

while (i <= mid) temp[k++] = arr[i++];
while (j <= h) temp[k++] = arr[j++];

for (int m = 0; m < temp.length; m++) {
arr[l + m] = temp[m];
}
}

void mergeSort(int[] arr, int n) {
for (int size = 1; size < n; size *= 2) {
for (int l = 0; l < n - size; l += 2 * size) {
int mid = l + size - 1;
int h = Math.min(l + 2 * size - 1, n - 1);
merge(arr, l, mid, h);
}
}
}
}

Approach 3: Using Built-in Sorting (For Comparison)

Arrays.sort(arr);

👉 Internally uses optimized algorithms (TimSort in Java)

Complexity Analysis

Time Complexity

CaseComplexity
BestO(n log n)
AverageO(n log n)
WorstO(n log n)

Space Complexity

  1. O(n) (extra array for merging)

Why Merge Sort is Powerful

  1. Stable sorting algorithm
  2. Works efficiently on large datasets
  3. Predictable performance
  4. Used in external sorting (large files)

❌ Why Not Use Bubble/Selection Sort?

AlgorithmTime Complexity
Bubble SortO(n²)
Selection SortO(n²)
Merge SortO(n log n) ✅

Key Takeaways

  1. Merge Sort uses divide and conquer
  2. Recursion splits problem into smaller parts
  3. Merging is the key step
  4. Always O(n log n), regardless of input

When to Use Merge Sort

  1. Large datasets
  2. Linked lists (very efficient)
  3. Stable sorting required
  4. External sorting

Conclusion

Merge Sort is one of the most reliable and efficient sorting algorithms. Understanding its recursive structure and merging process is essential for mastering advanced algorithms.

Once you grasp the divide-and-conquer pattern, it becomes easier to solve many complex problems.

Frequently Asked Questions (FAQs)

1. Is Merge Sort stable?

Yes, it maintains the relative order of equal elements.

2. Why is extra space required?

Because we use a temporary array during merging.

3. Can it be done in-place?

Not efficiently; standard merge sort requires extra space.

Related Articles

Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

Learn Quick Sort with detailed intuition, partition logic, Java code, dry run, and complexity analysis. Perfect for coding interviews and DSA.

Read Article
Sort a Stack Using Recursion - Java Solution Explained

Sort a Stack Using Recursion - Java Solution Explained

Learn how to sort a stack using recursion in Java. Includes intuition behind recursive sorting, insert in sorted position explained, step-by-step dry run, time & space complexity analysis.

Read Article
LeetCode 143 Reorder List - Java Solution Explained

LeetCode 143 Reorder List - Java Solution Explained

Learn how to solve LeetCode 143 Reorder List using Fast & Slow Pointer, Reverse Linked List, and Merge techniques in Java. Includes step-by-step dry run, time & space complexity analysis.

Read Article
Recursion in Java - Complete Guide With Examples and Practice Problems

Recursion in Java - Complete Guide With Examples and Practice Problems

Learn recursion in Java from scratch. Includes how recursion works, base case, recursive case, types of recursion, dry runs, time & space complexity, and top LeetCode problems with solutions.

Read Article
Ai Assistant Kas