Merge Sort in C++
Merge Sort in C++
Introduction
Merge Sort is a popular sorting algorithm that follows the Divide and Conquer approach. It divides an array into smaller subarrays, recursively sorts those subarrays, and finally merges the sorted subarrays to produce a completely sorted array.
In this tutorial, we will learn how to implement Merge Sort in C++. The program divides the array into two halves using the mid index, recursively sorts both halves, and then combines them using the merge() function. Merge Sort has a time complexity of O(n log n) in the best, average, and worst cases.
Table of Contents
- Algorithm
- C++ Program
- Input
- Sample Output
- Output
- Explanation
- Dry Run
- Flow of Execution
- Time Complexity
- Space Complexity
- Applications
- Key Points
- Interview Questions
- Frequently Asked Questions
- Keywords
- Conclusion
Algorithm
- Start the program.
- Read the size of the array.
- Read the array elements from the user.
- Call the mergeSort() function with low = 0 and high = num - 1.
- Check whether low < high.
- Calculate the middle index using mid = (low + high) / 2.
- Recursively divide the left half using mergeSort(a, low, mid).
- Recursively divide the right half using mergeSort(a, mid + 1, high).
- Call the merge() function to combine both sorted halves.
- Compare elements from the left and right halves.
- Copy the smaller element into the temporary array.
- Copy any remaining elements from the left half.
- Copy any remaining elements from the right half.
- Copy the elements from the temporary array back into the original array.
- Display the sorted array.
- Stop the program.
C++ Program
#include <iostream>
using namespace std;
void merge(int a[], int low, int mid, int high)
{
int temp[100];
int i = low;
int j = mid + 1;
int k = 0;
// Compare elements from both halves
while(i <= mid && j <= high)
{
if(a[i] <= a[j])
{
temp[k] = a[i];
i++;
}
else
{
temp[k] = a[j];
j++;
}
k++;
}
// Copy remaining elements from left half
while(i <= mid)
{
temp[k] = a[i];
i++;
k++;
}
// Copy remaining elements from right half
while(j <= high)
{
temp[k] = a[j];
j++;
k++;
}
// Copy temp back into original array
for(i = low, k = 0; i <= high; i++, k++)
{
a[i] = temp[k];
}
}
void mergeSort(int a[], int low, int high)
{
if(low < high)
{
int mid = (low + high) / 2;
// Divide left half
mergeSort(a, low, mid);
// Divide right half
mergeSort(a, mid + 1, high);
// Merge both sorted halves
merge(a, low, mid, high);
}
}
int main()
{
int num;
cout << "Enter the size of the array: ";
cin >> num;
int a[num];
cout << "Enter " << num << " elements: ";
for(int i = 0; i < num; i++)
{
cin >> a[i];
}
cout << "Before sorting: ";
for(int i = 0; i < num; i++)
{
cout << a[i] << " ";
}
mergeSort(a, 0, num - 1);
cout << "\nAfter sorting: ";
for(int i = 0; i < num; i++)
{
cout << a[i] << " ";
}
return 0;
}
Input
The program first accepts the size of the array and then reads the array elements from the user.
6
38
27
43
3
9
82
Sample Output
Enter the size of the array: 6
Enter 6 elements: 38 27 43 3 9 82
Before sorting: 38 27 43 3 9 82
After sorting: 3 9 27 38 43 82
Output
The program first displays the original array before sorting. The mergeSort() function then recursively divides the array into smaller halves and the merge() function combines the sorted halves. Finally, the completely sorted array is displayed in ascending order.
Explanation
Step 1
Include the required header file and use the standard namespace.
#include <iostream>
using namespace std;
- #include <iostream> provides input and output functions.
- using namespace std; allows us to use cin and cout without writing std::.
Step 2
Create the merge() function.
void merge(int a[], int low, int mid, int high)
{
int temp[100];
int i = low;
int j = mid + 1;
int k = 0;
}
- low represents the starting index.
- mid represents the middle index.
- high represents the ending index.
- The left half contains elements from low to mid.
- The right half contains elements from mid + 1 to high.
- temp is used to temporarily store the merged elements.
- i points to the current element of the left half.
- j points to the current element of the right half.
- k represents the current position in the temporary array.
Step 3
Compare elements from both sorted halves.
while(i <= mid && j <= high)
{
if(a[i] <= a[j])
{
temp[k] = a[i];
i++;
}
else
{
temp[k] = a[j];
j++;
}
k++;
}
- The loop continues while both halves contain elements.
- a[i] represents the current element in the left half.
- a[j] represents the current element in the right half.
- If a[i] <= a[j], the left element is copied into temp.
- Otherwise, the right element is copied into temp.
- The corresponding pointer is then moved forward.
- k is incremented after every insertion.
Step 4
Copy the remaining elements from the left half.
while(i <= mid)
{
temp[k] = a[i];
i++;
k++;
}
- This loop executes when the right half becomes empty first.
- Any remaining elements in the left half are already sorted.
- Therefore, they can be copied directly into the temporary array.
Step 5
Copy the remaining elements from the right half.
while(j <= high)
{
temp[k] = a[j];
j++;
k++;
}
- This loop executes when the left half becomes empty first.
- Any remaining elements in the right half are already sorted.
- They are copied directly into the temporary array.
Step 6
Copy the sorted elements from the temporary array back into the original array.
for(i = low, k = 0; i <= high; i++, k++)
{
a[i] = temp[k];
}
- The temporary array contains the merged elements in sorted order.
- The elements are copied back into the original array.
- The copying starts from index low and continues up to high.
- After this operation, the portion from low to high is sorted.
Step 7
Implement the mergeSort() function.
void mergeSort(int a[], int low, int high)
{
if(low < high)
{
int mid = (low + high) / 2;
mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
- The function works using recursion.
- if(low < high) checks whether the current portion contains more than one element.
- The middle index is calculated using mid = (low + high) / 2.
- The left half is recursively divided using mergeSort(a, low, mid).
- The right half is recursively divided using mergeSort(a, mid + 1, high).
- After both halves are sorted, merge() combines them.
Step 8
Read the array elements in the main() function.
int num;
cout << "Enter the size of the array: ";
cin >> num;
int a[num];
cout << "Enter " << num << " elements: ";
for(int i = 0; i < num; i++)
{
cin >> a[i];
}
- The user enters the size of the array.
- The array is created using the given size.
- A for loop reads all array elements.
Step 9
Display the array before sorting.
cout << "Before sorting: ";
for(int i = 0; i < num; i++)
{
cout << a[i] << " ";
}
This loop traverses the array and displays the original elements before Merge Sort is applied.
Step 10
Call the mergeSort() function.
mergeSort(a, 0, num - 1);
- 0 is the first index of the array.
- num - 1 is the last index of the array.
- The recursive Merge Sort process begins from the complete array.
- The array is repeatedly divided and then merged in sorted order.
Step 11
Display the sorted array.
cout << "\nAfter sorting: ";
for(int i = 0; i < num; i++)
{
cout << a[i] << " ";
}
After mergeSort() completes, the array contains elements in ascending order. The loop displays the final sorted array.
Dry Run
Input
38 27 43 3 9 82
Processing
| Operation | Array / Subarray | Explanation |
|---|---|---|
| Initial Array | 38 27 43 3 9 82 | The original array contains 6 elements. |
| Divide | 38 27 43 | 3 9 82 | The array is divided into two halves. |
| Divide Left | 38 | 27 43 | The left half is divided again. |
| Divide | 27 | 43 | The subarray is divided until individual elements are obtained. |
| Merge | 27 43 | 27 and 43 are already in sorted order. |
| Merge | 27 38 43 | 38 is merged with the sorted subarray. |
| Divide Right | 3 | 9 82 | The right half is divided. |
| Merge | 9 82 | 9 and 82 are merged in sorted order. |
| Merge | 3 9 82 | 3 is merged with the sorted subarray. |
| Final Merge | 3 9 27 38 43 82 | Both sorted halves are merged into the final sorted array. |
Output
Before sorting: 38 27 43 3 9 82
After sorting: 3 9 27 38 43 82
Flow of Execution
Start
│
▼
Read Array Size
│
▼
Read Array Elements
│
▼
Display Original Array
│
▼
Call mergeSort(0, n-1)
│
▼
low < high?
│ │
Yes No
│ │
▼ │
Calculate Mid │
│ │
▼ │
Divide Left Half │
│ │
▼ │
Divide Right Half │
│ │
▼ │
Merge Halves ◄─┘
│
▼
Sorted Array
│
▼
Display Result
│
▼
Stop
Time Complexity
| Case | Complexity |
|---|---|
| Best Case | O(n log n) |
| Average Case | O(n log n) |
| Worst Case | O(n log n) |
Overall Time Complexity: O(n log n)
Merge Sort divides the array into two halves recursively. The number of division levels is O(log n), and merging all elements at each level takes O(n) time. Therefore, the overall time complexity is O(n log n).
Space Complexity
- The temp array is used to store elements during merging.
- The temporary array requires additional memory proportional to the number of elements being merged.
- The recursive function calls also use stack memory.
Auxiliary Space Complexity: O(n)
Total Space Complexity: O(n)
Merge Sort requires additional memory for the temporary array used during the merge operation.
Applications
- Sorting large datasets efficiently.
- External sorting when data does not fit completely into memory.
- Sorting linked lists efficiently.
- Database systems and data processing applications.
- Inversion counting problems.
- Divide and Conquer based algorithmic problems.
- Stable sorting applications where the relative order of equal elements should be maintained.
- Large-scale data processing systems.
- Sorting data stored in external files.
- Learning the Divide and Conquer technique in Data Structures and Algorithms.
Key Points
- Merge Sort is a comparison-based sorting algorithm.
- It follows the Divide and Conquer approach.
- The array is recursively divided into smaller subarrays.
- The merge() function combines two sorted halves.
- The left half ranges from low to mid.
- The right half ranges from mid + 1 to high.
- The temporary array is used during the merge operation.
- Merge Sort has O(n log n) time complexity in the best, average, and worst cases.
- The implementation requires additional O(n) auxiliary space.
- Merge Sort can efficiently handle large datasets.
- Merge Sort is a stable sorting algorithm when the merge condition uses <=.
Interview Questions
- What is Merge Sort?
- Which algorithmic technique does Merge Sort use?
- What is the Divide and Conquer approach?
- What is the purpose of the merge() function?
- What is the purpose of the mid variable?
- Why are two recursive calls used in mergeSort()?
- How are the left and right halves identified?
- What is the time complexity of Merge Sort?
- What is the space complexity of Merge Sort?
- What is the best-case time complexity of Merge Sort?
- What is the worst-case time complexity of Merge Sort?
- Why is a temporary array used in Merge Sort?
- Is Merge Sort a stable sorting algorithm?
- What is the difference between Merge Sort and Bubble Sort?
- What is the difference between Merge Sort and Quick Sort?
- Why is Merge Sort useful for sorting large datasets?
Frequently Asked Questions (FAQs)
1. What is Merge Sort?
Merge Sort is a sorting algorithm that uses the Divide and Conquer technique. It recursively divides an array into smaller parts and then merges the sorted parts.
2. What is the main idea behind Merge Sort?
The main idea is to divide the array into two halves, recursively sort both halves, and then merge the two sorted halves into one sorted array.
3. What is the time complexity of Merge Sort?
Merge Sort has a time complexity of O(n log n) in the best, average, and worst cases.
4. What is the space complexity of Merge Sort?
The implementation requires O(n) auxiliary space because a temporary array is used during the merge operation.
5. What is the purpose of the merge() function?
The merge() function combines two already sorted halves into one sorted portion of the array.
6. Why is Merge Sort called a Divide and Conquer algorithm?
It is called Divide and Conquer because it divides the problem into smaller subproblems, solves them recursively, and combines their results.
7. Is Merge Sort stable?
Yes. Merge Sort can be stable. In this implementation, the condition a[i] <= a[j] ensures that equal elements from the left half are selected before equal elements from the right half.
8. Does Merge Sort modify the original array?
Yes. After the merging process, the sorted elements stored in the temporary array are copied back into the original array.
9. Why are the remaining elements copied after the main while loop?
The main comparison loop stops when one of the two halves becomes empty. Since the remaining elements in the other half are already sorted, they can be copied directly into the temporary array.
10. Why is Merge Sort useful?
Merge Sort provides predictable O(n log n) time complexity and is especially useful for large datasets and applications where stable sorting is required.
Keywords
Merge Sort in C++, Merge Sort Program in C++, Merge Sort Algorithm, Merge Sort Using Divide and Conquer, Merge Sort DSA, Merge Sort Code, Sorting Algorithms in C++, Divide and Conquer Algorithm, Merge Sort Interview Questions, Merge Sort Time Complexity, Merge Sort Space Complexity, C++ Sorting Programs, Merge Function in C++, Recursive Sorting Algorithm, Stable Sorting Algorithm, Data Structures and Algorithms in C++.
Conclusion
In this tutorial, we learned how to implement Merge Sort in C++ using the Divide and Conquer approach. The algorithm recursively divides the array into smaller halves and uses the merge() function to combine the sorted halves. Merge Sort provides a consistent O(n log n) time complexity for the best, average, and worst cases. Although it requires additional memory for the temporary array, it is an efficient and important sorting algorithm for large datasets. Understanding Merge Sort also provides a strong foundation for learning other Divide and Conquer algorithms and advanced Data Structures and Algorithms concepts.
Comments
Post a Comment