Merge Sort Algorithm – Step by Step Explanation with Example, Time Complexity & Diagram

 

Merge Sort Algorithm – Step by Step Explanation with Example and Time Complexity

Introduction

Merge Sort is one of the most important sorting algorithms in Data Structures. It follows the Divide and Conquer technique.

Merge Sort is widely used because:

• It is efficient for large datasets

• It has consistent time complexity

• It is stable

In this article, we will learn:

• What is Merge Sort

• How it works

• Step-by-step example

• Time complexity

• Advantages and disadvantages

• Comparison table

• Exam questions

---

What is Merge Sort?

Merge Sort is a sorting algorithm that:

1. Divides the array into two halves

2. Recursively sorts both halves

3. Merges the sorted halves

It continues dividing until each subarray contains only one element.

Then it merges them back in sorted order.

---

How Merge Sort Works (Step-by-Step)

Let’s take an example:

Array:

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

---

Step 1: Divide

Split into two halves:

Left:

[38, 27, 43]

Right:

[3, 9, 82, 10]

---

Step 2: Divide Again

Left becomes:

[38] [27, 43]

Right becomes:

[3, 9] [82, 10]

Continue dividing until single elements.

---

Step 3: Merge and Sort

Merge small parts in sorted order:

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

Finally merge everything:

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

Sorted array obtained.

---

Why Merge Sort is Efficient

At each level:

• The array is divided into halves

• Total merging work = n elements

Number of levels = log n

Therefore:

👉 Time Complexity = O(n log n)

---

Time Complexity of Merge Sort

Case	Time Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)

Unlike Quick Sort, Merge Sort has consistent performance.

---

Space Complexity

Merge Sort requires extra memory for merging.

Space Complexity:
👉 O(n)

Because it creates temporary arrays.

---

Advantages of Merge Sort

✔ Stable sorting algorithm
✔ Predictable performance
✔ Efficient for large datasets
✔ Works well for linked lists

---

Disadvantages of Merge Sort

❌ Requires extra memory
❌ Slower for small datasets compared to simple sorts
❌ Recursive calls increase overhead

---

Merge Sort vs Bubble Sort

Feature	Merge Sort	Bubble Sort
Time Complexity	O(n log n)	O(n²)
Stable	Yes	Yes
Efficient for large data	Yes	No
Extra Space	Yes	No

Merge Sort is much faster for large inputs.

---

Real-Life Applications

Merge Sort is used in:

• Sorting large databases

• External sorting

• Big data processing

• Programming language libraries

• Divide and conquer problems                                                                                                            

  Pseudocode (Exam Friendly)

  MergeSort(arr):
      if length(arr) > 1:
          mid = length(arr)/2
          left = arr[0:mid]
          right = arr[mid:]
  
          MergeSort(left)
          MergeSort(right)
  
          Merge(left, right)
  

  ---

  Conclusion

  Merge Sort is one of the most powerful and efficient sorting algorithms in Data Structures. Its predictable O(n log n) time complexity makes it suitable for large datasets.

  Although it requires extra space, its stability and performance make it widely used in real-world applications.

  Understanding Merge Sort is essential for semester exams, coding interviews, and algorithm design.

👉 Also Read:

• Sorting Algorithms in Data Structures

• Time Complexity – Big O Notation Explained

• Linear Search vs Binary Search  

• to read the other topics related to this u can refer my blog acc