Merge Sort is one of the most efficient sorting algorithms, known for its consistent O(n log n) time complexity and stable sorting characteristics. It’s particularly useful when dealing with large datasets or when stability is important in sorting. In this blog post, we’ll explore Merge Sort, explain how it works, implement it in C++, and analyze its performance compared to Bubble Sort.
Introduction to Merge Sort
Merge Sort is a comparison-based sorting algorithm that uses the divide-and-conquer strategy. It splits the input array into smaller subarrays, sorts them, and merges them back together to form the sorted array. Merge Sort is widely used due to its efficiency and stability, making it a popular choice for applications where consistent performance and relative order of equal elements need to be preserved.
Time Complexity:
- Best, Average, and Worst Case: O(n log n)
Stability:
- Merge Sort is stable, meaning that two equal elements will maintain their relative order in the sorted output.
Space Complexity:
- Merge Sort requires additional space proportional to the size of the input array, making its space complexity O(n).
How Merge Sort Works
Merge Sort follows the divide-and-conquer approach, splitting the array into smaller subarrays, sorting them individually, and merging them back together. The array is recursively divided until single elements are left, which are inherently sorted, and then these sorted subarrays are merged.
Steps:
- Divide: Split the array into two halves.
- Recursion: Recursively sort both halves.
- Merge: Combine the two sorted halves to form the sorted array.
Merge Sort Pseudocode
Here is the simplified pseudocode for Merge Sort:
function mergeSort(arr, left, right):
if left < right:
mid = (left + right) / 2
mergeSort(arr, left, mid)
mergeSort(arr, mid + 1, right)
merge(arr, left, mid, right)
function merge(arr, left, mid, right):
Create temporary arrays L and R
Copy data into L and R
Merge L and R back into arr[left...right]
Merge Sort Implementation in C++
Here’s a step-by-step implementation of Merge Sort in C++:
#include <iostream>
#include <vector>
using namespace std;
// Function to merge two halves of the array
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
vector<int> L(n1), R(n2);
// Copy data into temporary arrays L and R
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int i = 0; i < n2; i++)
R[i] = arr[mid + 1 + i];
// Merge the two arrays back into arr[left...right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L, if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R, if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Function to implement Merge Sort
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Sort the first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
// Function to print the array
void printArray(const vector<int>& arr) {
for (int num : arr)
cout << num << " ";
cout << endl;
}
int main() {
vector<int> arr = {12, 11, 13, 5, 6, 7};
cout << "Original array: ";
printArray(arr);
mergeSort(arr, 0, arr.size() - 1);
cout << "Sorted array: ";
printArray(arr);
return 0;
}
Output:
Original array: 12 11 13 5 6 7 Sorted array: 5 6 7 11 12 13
Performance Testing Merge Sort
Merge Sort performs consistently well across all types of input (random, sorted, reverse-sorted) because of its time complexity of O(n log n). Let’s run performance tests on different input sizes and data types.
Test Setup:
- Random Array: Unordered elements.
- Sorted Array: Already sorted elements (best case).
- Reverse-Sorted Array: Elements sorted in descending order (worst case for many algorithms).
Code for Performance Testing
We’ll use the <chrono> library to measure the time taken by Merge Sort on different datasets.
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm> // For std::shuffle
#include <random>
using namespace std;
// Merge function to merge two halves of the array
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
vector<int> L(n1), R(n2);
// Copy data into temporary arrays L and R
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int i = 0; i < n2; i++)
R[i] = arr[mid + 1 + i];
// Merge the two arrays back into arr[left...right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L, if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R, if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Merge Sort function
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Sort the first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
// Function to perform and time Merge Sort
double testMergeSort(vector<int> arr) {
auto start = chrono::high_resolution_clock::now();
mergeSort(arr, 0, arr.size() - 1);
auto end = chrono::high_resolution_clock::now();
chrono::duration<double, micro> duration = end - start;
return duration.count(); // Return time in microseconds
}
// Function to generate an array of a given type and size
vector<int> generateArray(int size, const string& type) {
vector<int> arr(size);
for (int i = 0; i < size; i++) {
arr[i] = i + 1;
}
if (type == "random") {
shuffle(arr.begin(), arr.end(), default_random_engine(random_device()()));
} else if (type == "reverse") {
reverse(arr.begin(), arr.end());
}
return arr;
}
int main() {
vector<string> types = {"random", "sorted", "reverse"};
vector<int> sizes = {1000, 5000, 10000};
cout << "Merge Sort Performance Testing:\n";
cout << "Array Size\tType\t\tTime (μs)\n";
for (int size : sizes) {
for (const string& type : types) {
vector<int> arr = generateArray(size, type);
double time = testMergeSort(arr);
cout << size << "\t\t" << type << "\t\t" << time << endl;
}
}
return 0;
}
Output:
Merge Sort Performance Testing: Array Size Type Time (μs) 1000 random 819.168 1000 sorted 743.548 1000 reverse 759.825 5000 random 5074.94 5000 sorted 5099.81 5000 reverse 5331.93 10000 random 11583.5 10000 sorted 10288.9 10000 reverse 10409.9
Key Takeaways from Merge Sort Performance Testing Results:
- Consistent Performance Across Array Types:
- Merge Sort demonstrates consistent performance regardless of the input type (random, sorted, or reverse). The time difference between random, sorted, and reverse-sorted arrays is minimal, showing that Merge Sort does not benefit significantly from already sorted data.
- For example, for an array size of 1000, the time taken for random data is 819.168 μs, for sorted data 743.548 μs, and for reverse-sorted data 759.825 μs, all very close.
- Scalability with Larger Arrays:
- As the array size increases from 1000 to 10000, the time taken by Merge Sort increases proportionally. This is consistent with the O(n log n) time complexity, which ensures efficient scaling even for larger datasets.
- For a 1000-element array, the times are under 1000 μs, while for a 10000-element array, the times increase to around 10,000-11,500 μs, reflecting the logarithmic growth of the algorithm.
- Negligible Difference for Best, Worst, and Average Cases:
- Merge Sort is largely unaffected by the order of the elements in the input array. For an array size of 5000, the times for random, sorted, and reverse-sorted arrays are 5074.94 μs, 5099.81 μs, and 5331.93 μs respectively, demonstrating that Merge Sort treats all input types similarly.
- This makes Merge Sort a reliable choice for datasets where the input order is unpredictable.
- Stable Performance Across Input Sizes:
- The difference in time between sorted and unsorted arrays remains small even as the input size grows, reflecting the consistency of Merge Sort’s performance. For a 10000-element array, the times are 11583.5 μs (random), 10288.9 μs (sorted), and 10409.9 μs (reverse), indicating that Merge Sort maintains its efficiency regardless of input type and size.
- Merge Sort’s Predictable Behavior:
- Merge Sort’s performance remains predictable and stable, making it an excellent choice for situations where you need guaranteed efficiency. It consistently outperforms less efficient algorithms like Bubble Sort, especially on larger datasets, without any significant performance drops due to input order.
Merge Sort vs. Bubble Sort Performance Comparison
When comparing Merge Sort and Bubble Sort, it’s important to consider their time complexities and how they perform on different types of input data. Both algorithms are used for sorting, but their efficiency and suitability for larger datasets are vastly different.
Bubble Sort Overview:
- Time Complexity:
- Best Case: O(n) (if the array is already sorted)
- Worst and Average Case: O(n²)
- Space Complexity: O(1) (no additional memory required, in-place sort)
- Stability: Stable (preserves the relative order of equal elements)
Bubble Sort is a simple, comparison-based algorithm that repeatedly steps through the list, swaps adjacent elements if they are in the wrong order, and gradually bubbles the largest elements to the end of the list.
Merge Sort Overview:
- Time Complexity:
- Best, Average, and Worst Case: O(n log n)
- Space Complexity: O(n) (requires additional space for temporary arrays)
- Stability: Stable (preserves the relative order of equal elements)
Merge Sort is an efficient, divide-and-conquer algorithm that recursively splits the array into smaller subarrays, sorts them, and merges them back together.
Performance Comparison
To clearly understand the difference in performance between Merge Sort and Bubble Sort, let’s compare their execution times on various input sizes. We’ll use the same testing setup from before, and now include Bubble Sort in the comparison.
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm> // For std::shuffle
#include <random>
using namespace std;
// Merge function to merge two halves of the array
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
vector<int> L(n1), R(n2);
// Copy data into temporary arrays L and R
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int i = 0; i < n2; i++)
R[i] = arr[mid + 1 + i];
// Merge the two arrays back into arr[left...right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L, if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R, if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Merge Sort function
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Sort the first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
// Function to perform and time Merge Sort
double testMergeSort(vector<int> arr) {
auto start = chrono::high_resolution_clock::now();
mergeSort(arr, 0, arr.size() - 1);
auto end = chrono::high_resolution_clock::now();
chrono::duration<double, micro> duration = end - start;
return duration.count(); // Return time in microseconds
}
// Bubble Sort function for comparison
void bubbleSort(vector<int>& arr) {
int n = arr.size();
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) // If no swaps occurred, the array is sorted
break;
}
}
// Function to perform and time Bubble Sort
double testBubbleSort(vector<int> arr) {
auto start = chrono::high_resolution_clock::now();
bubbleSort(arr);
auto end = chrono::high_resolution_clock::now();
chrono::duration<double, micro> duration = end - start;
return duration.count(); // Return time in microseconds
}
// Function to generate an array of a given type and size
vector<int> generateArray(int size, const string& type) {
vector<int> arr(size);
for (int i = 0; i < size; i++) {
arr[i] = i + 1;
}
if (type == "random") {
shuffle(arr.begin(), arr.end(), default_random_engine(random_device()()));
} else if (type == "reverse") {
reverse(arr.begin(), arr.end());
}
return arr;
}
int main() {
vector<string> types = {"random", "sorted", "reverse"};
vector<int> sizes = {1000, 5000, 10000};
cout << "Performance Comparison - Merge Sort vs Bubble Sort:\n";
cout << "Array Size\tType\t\tMerge Sort (μs)\tBubble Sort (μs)\n";
for (int size : sizes) {
for (const string& type : types) {
vector<int> arr1 = generateArray(size, type); // For Merge Sort
vector<int> arr2 = arr1; // For Bubble Sort
double mergeSortTime = testMergeSort(arr1);
double bubbleSortTime = testBubbleSort(arr2);
cout << size << "\t\t" << type << "\t\t" << mergeSortTime << "\t\t" << bubbleSortTime << endl;
}
}
return 0;
}
Explanation:
- mergeSort Function: The merge sort algorithm is fully included in the performance testing code.
- testMergeSort Function: This function is responsible for timing how long Merge Sort takes on a given dataset.
- Bubble Sort: We also include a bubble sort implementation and a performance function (
testBubbleSort) to compare the times of both sorting algorithms. - generateArray Function: This generates arrays of varying sizes and types (random, sorted, reverse) for testing.
Output:
Performance Comparison - Merge Sort vs Bubble Sort: Array Size Type Merge Sort (μs) Bubble Sort (μs) 1000 random 1096.49 5877.69 1000 sorted 1052.15 5.358 1000 reverse 971.804 6278.71 5000 random 6073.05 150963 5000 sorted 5166.05 23.981 5000 reverse 5013.27 145752 10000 random 55115.9 685777 10000 sorted 11155 49.628 10000 reverse 10547.9 677824
Key Takeaways from the Performance Comparison – Merge Sort vs. Bubble Sort:
- Merge Sort’s Consistent Performance Across Input Types:
- Merge Sort maintains consistent performance regardless of the input type (random, sorted, reverse). For instance, with a 1000-element array, Merge Sort takes around 1000–1100 μs, while for a 5000-element array, it takes around 5000–6000 μs across different input types. This shows the stability of its O(n log n) time complexity.
- Bubble Sort’s Best Case on Sorted Arrays:
- Bubble Sort performs exceptionally well on sorted arrays due to its optimization that stops early if no swaps are needed. For sorted data, it completes in 5.358 μs (1000 elements) and 23.981 μs (5000 elements), which is much faster than Merge Sort. This indicates that in rare cases where the data is already sorted, Bubble Sort can be advantageous.
- Bubble Sort’s Poor Performance on Large and Unsorted Data:
- For random and reverse-sorted data, Bubble Sort’s performance is significantly worse. For a 10000-element random array, Bubble Sort takes 685777 μs, compared to Merge Sort’s 55115.9 μs. The quadratic time complexity (O(n²)) of Bubble Sort leads to massive increases in execution time as the array size grows.
- Merge Sort’s Superior Scalability:
- Merge Sort scales much better with larger datasets. For a 10000-element array, Merge Sort consistently outperforms Bubble Sort, regardless of the data type. It finishes in about 10,000–55,000 μs, while Bubble Sort can take as long as 677,000–685,000 μs for random and reverse-sorted data, highlighting its inefficiency with larger datasets.
- Input Sensitivity of Bubble Sort:
- Bubble Sort shows extreme variability depending on the input type. While it is very fast for sorted arrays, it becomes exceedingly slow for random and reverse-sorted data, making it impractical for most real-world applications where the data order is unknown.
Summary:
Overall, Merge Sort is vastly more efficient and scalable for all types of data, while Bubble Sort is only suitable for very small, already sorted datasets. Merge Sort’s O(n log n) complexity ensures it handles large datasets effectively, whereas Bubble Sort’s O(n²) complexity makes it unsuitable for general use with large or unsorted data.
Why and How Performance Testing Numbers Can Change
Performance testing numbers can vary due to several factors:
- Hardware Specifications: The CPU, memory, and overall system performance can significantly impact the sorting times. A more powerful CPU will naturally result in faster sorting times.
- System Load: The performance of sorting algorithms can change if the system is running multiple tasks. Background processes or other resource-heavy tasks may slow down the execution of your sorting algorithm.
- Compiler Optimizations: The compiler’s optimization flags (e.g.,
-O2,-O3in GCC) can influence the speed of the algorithm. Higher optimization levels can lead to faster execution times. - Random Variations in Input: Small changes in the randomized input can cause minor differences in execution time. While Merge Sort is consistent, small variations in the order of elements can slightly affect the time.
- Cache Effects: The size of the input and how well it fits into the CPU cache can also impact performance. Algorithms like Merge Sort may benefit from cache locality more than Bubble Sort.
Thus, while the general trend (Merge Sort being faster than Bubble Sort) remains constant, the exact numbers can fluctuate depending on these factors.
Applications of Merge Sort
Merge Sort is used in various scenarios, including:
- Sorting Linked Lists: Merge Sort is highly efficient for linked lists because it does not require random access to elements.
- External Sorting: It is used when data does not fit into memory, as Merge Sort works efficiently with disk storage.
- Stable Sorting: Merge Sort is stable, making it a good choice for sorting data with multiple attributes, where relative order needs to be preserved.
Merge Sort is a highly efficient and reliable algorithm for sorting data, particularly when the dataset is large or the input order is unknown. Its O(n log n) time complexity ensures consistent performance across all input types—random, sorted, and reverse-sorted. This makes Merge Sort an excellent choice for real-world applications where predictable and scalable performance is needed. Additionally, Merge Sort is stable, meaning it preserves the relative order of equal elements, which is important in many scenarios.
Congratulations on reading to the end of this tutorial!
To implement Merge Sort in Python, go to the article: How to do Merge Sort in Python.
For performance comparisons between Quick Sort and TimSort, go to How To Do TimSort in C++.
For further reading on sorting algorithms in C++, go to the articles:
- Shell Sort in C++
- How To Do Quick Sort in C++
- How To Do Selection Sort in C++
- How To Do Comb Sort in C++
- How To Do Insertion Sort in C++
Have fun and happy researching!
Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.