Merge Sort Algorithm

Merge Sort is a divide-and-conquer based sorting algorithm that divides a list into smaller parts, sorts them, and merges them to produce a final sorted list. Learn definition, steps, example, time and space complexity, advantages, disadvantages, and applications.

Merge Sort Algorithm:

What is Merge Sort?

Merge Sort is a sorting algorithm based on the Divide and Conquer technique.
It divides a large array/list into smaller parts, sorts each part, and then merges those sorted parts together.

In simple terms:

Divide → Sort → Merge → Sorted List

Main Steps of Merge Sort

1Divide

• Divide the array into two equal parts
• Keep dividing each part into smaller parts
• Continue until each part contains only one element

2Conquer / Sort

• A part with a single element is already sorted
• While combining back, these small parts get sorted automatically

3 Merge

• Combine two sorted sub-arrays
• Place elements in ascending order
• Finally, the complete array becomes sorted

Simple Example

Consider the array:

8 3 5 2

Step 1 — Divide

8 3 5 2
→ 8 3 | 5 2
→ 8 | 3 | 5 | 2

Step 2 — Sort small parts

8 → sorted
3 → sorted
5 → sorted
2 → sorted

Step 3 — Merge

8 and 3 → 3 8
5 and 2 → 2 5

Then:

3 8 and 2 5 → 2 3 5 8

Why does Merge Sort work?

Because:

• Smaller problems are easier to solve
• Sorting happens during merging
• Elements are placed in the correct position at every level

Time Complexity

Performance remains the same in all cases — this is a major advantage.

Space Complexity

Merge Sort requires extra memory:

O(n)

because a separate array is used during merging.

Advantages of Merge Sort

• Always O(n log n) performance
• Very useful for large datasets
• Stable sorting algorithm
• Excellent for linked lists

Disadvantages of Merge Sort

Requires extra memory
Slightly difficult to implement
Slower than Quick Sort for small datasets

Where is Merge Sort used?

• Large datasets
• External sorting (data stored on hard disk)
• File-merging systems
• Database sorting
• Linked list sorting

Summary

Merge Sort sorts a large list by dividing it into smaller parts, sorting them, and then merging them to form the final sorted list.

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1