Merge Sort is one of the most fundamental sorting algorithms taught in computer science and is an essential part of the B.Tech Data Structures Notes 2025. As part of Unit 2 Notes Data Structures, Merge Sort embodies the efficiency and conceptual clarity of the divide and conquer strategy. It offers stable and predictable performance even in the worst-case scenarios, making it a popular choice not just in academics but in many real-world systems. Merge Sort splits the input array into halves, sorts them recursively, and merges the sorted halves to produce the final sorted array.
Definition: Merge Sort is a comparison-based sorting technique based on the Divide and Conquer strategy, where the problem is divided into smaller sub-problems (divide), solved recursively (conquer), and combined (merge) to form the final solution.
The three key steps of the Divide and Conquer approach in Merge Sort are:
- Divide: The unsorted list is divided into
nsublists, each containing one element, because a list of one element is considered sorted. - Conquer: Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This final sublist is the sorted list.
- Combine: The merging process is where the sorting actually takes place. Elements from the divided sublists are compared and merged into a sorted form.
Let us understand the step-by-step execution and implementation of Merge Sort.
Working of Merge Sort Algorithm
The core idea of Merge Sort lies in its recursive division and systematic merging. Suppose we have an array A = [38, 27, 43, 3, 9, 82, 10].
- Initial array: [38, 27, 43, 3, 9, 82, 10]
- Divide into halves: [38, 27, 43] and [3, 9, 82, 10]
- Further division:
- [38, 27, 43] becomes [38] and [27, 43]
- [27, 43] becomes [27] and [43]
- [3, 9, 82, 10] becomes [3, 9] and [82, 10]
- [3, 9] becomes [3] and [9], [82, 10] becomes [82] and [10]
Now, we start merging:
- Merge [27] and [43] into [27, 43]
- Merge [38] and [27, 43] into [27, 38, 43]
- Merge [3] and [9] into [3, 9]
- Merge [82] and [10] into [10, 82]
- Merge [3, 9] and [10, 82] into [3, 9, 10, 82]
- Merge [27, 38, 43] and [3, 9, 10, 82] into final sorted array: [3, 9, 10, 27, 38, 43, 82]
📌 Insert Diagram: Recursive Division and Merge of Merge Sort on [38, 27, 43, 3, 9, 82, 10]
Algorithm (Pseudocode)
MERGE_SORT(arr, left, right):
if left < right:
mid = (left + right) / 2
MERGE_SORT(arr, left, mid)
MERGE_SORT(arr, mid+1, right)
MERGE(arr, left, mid, right)
MERGE(arr, left, mid, right):
create temporary arrays L and R
copy data into L[] and R[]
while both arrays have elements:
compare and merge into main array
copy remaining elements (if any)Time and Space Complexity Analysis
| Case | Time Complexity |
|---|---|
| Best Case | O(n log n) |
| Average | O(n log n) |
| Worst Case | O(n log n) |
- Space Complexity: O(n) due to auxiliary arrays used during merging.
- Stable Sort: Yes, Merge Sort maintains the relative order of equal elements.
C Program Implementation of Merge Sort
#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr)/sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}Applications of Merge Sort
Merge Sort is particularly useful in scenarios where stable sorting is required or when working with large datasets on external storage. Some notable applications include:
- Sorting linked lists (Merge Sort works better than Quick Sort due to non-contiguous memory)
- External sorting (e.g., merge sort is used in external memory algorithms)
- Parallel sorting implementations in distributed systems
🔹 Short Answer Questions (2-3 Marks)
- Define Merge Sort.
Merge Sort is a divide-and-conquer-based sorting algorithm that recursively splits an array and merges sorted halves. - What is the time complexity of Merge Sort in the best case?
O(n log n) - Is Merge Sort stable?
Yes, Merge Sort is a stable sorting algorithm. - Which programming paradigm does Merge Sort follow?
Divide and Conquer. - Why is Merge Sort better than Quick Sort in linked lists?
Because it does not require random access and works well with sequential memory. - What is the space complexity of Merge Sort?
O(n) - Can Merge Sort be implemented iteratively?
Yes, though recursive implementation is more common and easier to understand.
🔸 Long Answer Questions (5-10 Marks)
- Explain the working of Merge Sort with the help of a suitable example.
Merge Sort first divides the array into two halves recursively until each part has a single element. These parts are then merged in a sorted manner by comparing and ordering the elements. For example, given [38, 27, 43, 3, 9, 82, 10], the algorithm performs recursive division and then merges: first [38] and [27] into [27, 38], [43] is then merged to form [27, 38, 43], and similarly for other half arrays. Finally, the two sorted halves are merged to form the sorted array [3, 9, 10, 27, 38, 43, 82]. - Write and explain the Merge Sort algorithm in detail.
The algorithm uses recursive calls to break the array. Each call divides the array into two halves and sorts them individually. Themerge()function then combines them in a sorted order. Detailed pseudocode and the actual code implementation have been provided above. - Compare Merge Sort with Quick Sort in terms of time and space complexity.
Merge Sort has consistent time complexity of O(n log n) in all cases but needs O(n) auxiliary space. Quick Sort has average case O(n log n) but a worst-case of O(n^2), although it requires only O(log n) space. - Describe real-world applications where Merge Sort is preferred.
Merge Sort is preferred in external sorting, stable sorting, and linked list sorting due to its stability and non-reliance on random memory access.
📝 Chapter Summary
Merge Sort is a divide and conquer sorting algorithmDivide step recursively splits the array into halvesConquer step merges the sorted halvesMerge function involves comparing elements and combining themTime complexity is O(n log n) for all casesSpace complexity is O(n) due to extra arraysMerge Sort is stable and predictableIt is useful in scenarios like linked list sorting, external memory sortingRecursive and iterative implementations are possible
📘 Model Paper / Sample Internal Exam Questions
- Explain the working of Merge Sort algorithm using the divide and conquer approach.
- Write the C code for implementing Merge Sort.
- What are the advantages and disadvantages of Merge Sort compared to other sorting techniques?
- Explain Merge Sort with time complexity analysis for different cases.
- Compare Merge Sort with Quick Sort and mention which one is better under what circumstances.
