Merge Sort Algorithm in C++
Introduction
Merge Sort is a popular sorting algorithm that follows the divide-and-conquer paradigm. It's an efficient and stable sorting algorithm that works by dividing an array into two halves, sorting each half, and then merging the sorted halves to produce a single sorted array. This process is repeated recursively until the entire array is sorted.
In this article, we'll provide a C++ implementation of the Merge Sort algorithm and explain how it works step by step.
Merge Sort Algorithm
The Merge Sort algorithm can be broken down into two main steps:
Divide: The algorithm begins by dividing the original array into two halves. This division is done recursively, effectively breaking the problem into smaller and smaller sub-problems until each sub-array has only one element. This is the base case for recursion.
Conquer (Merge): After the array is divided into single-element sub-arrays, the algorithm starts merging them. Merging involves comparing elements in the two sub-arrays, picking the smaller element first, and placing it into the new merged array. This process continues until all the sub-arrays are merged into a single sorted array.
Merge Sort can be implemented in two main approaches: the top-down approach and the bottom-up approach. These methods differ in how they break down and combine the elements for sorting. Let's explain both approaches:
Top-Down Merge Sort:
- Divide: The array is recursively divided into two halves until each sub-array contains only one element. This is done by finding the middle index and splitting the array into left and right halves.
- Conquer: The individual elements are considered sorted when there's only one element in each sub-array. Then, pairs of sub-arrays are merged together to create larger sorted sub-arrays. This merging process continues recursively until the entire array is sorted.
- Merge: When merging two sub-arrays, you compare the elements in the two arrays to create a merged, sorted array. The smaller of the two elements is chosen and placed in the merged array. This process continues for all elements in both arrays.
- Repeat: Steps 1 to 3 are repeated for all levels of recursion until the entire array is sorted.
The top-down approach is more intuitive and closely resembles the high-level description of the Merge Sort algorithm. It often uses recursive function calls to achieve the sorting.
Bottom-Up Merge Sort:
- Iterative Sorting: In the bottom-up approach, the sorting process begins with small sub-arrays containing one element each. These single-element sub-arrays are considered sorted.
- Iterative Merging: Pairs of these single-element sub-arrays are merged to create larger sub-arrays. Then, pairs of those sub-arrays are merged, and this process continues iteratively.
- Final Merge: The merging continues until the entire array is sorted.
The bottom-up approach does not rely on recursive function calls but instead uses iterative loops. It starts by considering the smallest sub-arrays as sorted and gradually merges them to create larger sorted sub-arrays, eventually producing a fully sorted array.
History of Merge Sort
The Merge Sort algorithm was developed by John von Neumann in 1945 as part of a report on the foundations for a new digital computer called the Electronic Computer Project at the Institute for Advanced Study in Princeton, New Jersey. The project was initiated during World War II and aimed to create a high-speed computer capable of performing complex calculations.
- Development by John von Neumann (1945): John von Neumann, a brilliant mathematician and computer scientist, developed the Merge Sort algorithm during his work on the Electronic Computer Project. He used the algorithm as part of the project's software design to efficiently sort data.
- Initial Implementation (1945-1950s): The Merge Sort algorithm was one of the earliest sorting algorithms to be implemented and used on early digital computers. During this period, it was a valuable tool for scientific and engineering applications.
- Theoretical and Practical Advancements (1960s-1980s): Merge Sort, along with other sorting algorithms, underwent further theoretical and practical refinements. Researchers and computer scientists studied its time and space complexity and made improvements to its performance.
- Incorporation into Standard Libraries (1980s-Present): Merge Sort has been widely adopted as one of the standard sorting algorithms and is often included in standard libraries for various programming languages and platforms. Its stable nature and predictable performance make it a reliable choice for a wide range of applications.
- Continued Relevance (Present): Merge Sort remains a significant sorting algorithm used in various fields, including computer science, data processing, and software development. It is valued for its efficiency and stability, and it is a fundamental concept in the study of algorithms.
Example 1 - Merge Sort for Sorting Integers:
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays to hold the two halves
std::vector<int> leftHalf(n1);
std::vector<int> rightHalf(n2);
// Copy data to temporary arrays leftHalf[] and rightHalf[]
for (int i = 0; i < n1; i++) {
leftHalf[i] = arr[left + i];
}
for (int i = 0; i < n2; i++) {
rightHalf[i] = arr[mid + 1 + i];
}
// Merge the two halves back into arr[]
int i = 0; // Initial index of the first subarray
int j = 0; // Initial index of the second subarray
int k = left; // Initial index of the merged subarray
while (i < n1 && j < n2) {
if (leftHalf[i] <= rightHalf[j]) {
arr[k] = leftHalf[i];
i++;
} else {
arr[k] = rightHalf[j];
j++;
}
k++;
}
// Copy the remaining elements of leftHalf[], if any
while (i < n1) {
arr[k] = leftHalf[i];
i++;
k++;
}
// Copy the remaining elements of rightHalf[], if any
while (j < n2) {
arr[k] = rightHalf[j];
j++;
k++;
}
}
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
// Find the middle point
int mid = left + (right - left) / 2;
// Recursively sort the first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
int arrSize = arr.size();
std::cout << "Original array: ";
for (int i = 0; i < arrSize; i++) {
std::cout << arr[i] << " ";
}
mergeSort(arr, 0, arrSize - 1);
std::cout << "\nSorted array: ";
for (int i = 0; i < arrSize; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
Explanation
- The merge function is responsible for merging two sorted sub-arrays back into a single sorted array. It takes as parameters the original array arr, the indices that define the left (left) and right (right) sub-arrays, and the index (mid) that separates them.
- Inside the merge function, we create two temporary arrays, leftHalf and rightHalf, to hold the elements of the left and right sub-arrays.
- We then copy the data from the original array arr into these temporary arrays.
- The actual merging of the two sub-arrays happens in the while loop, where we compare the elements from leftHalf and rightHalf and place the smaller element back in the original array arr.
- The mergeSort function is the main function for sorting the array. It follows the divide-and-conquer approach by recursively dividing the array into smaller halves until they contain only one element. Then, it merges these smaller sorted arrays using the merge function.
Key characteristics of Merge Sort:
- Stability: Merge Sort is a stable sorting algorithm, meaning that the relative order of equal elements in the sorted array remains the same as in the original unsorted array.
- Efficiency: Merge Sort has a time complexity of O (n log n), making it suitable for sorting large datasets. It is a good general-purpose sorting algorithm.
- Additional Memory: Merge Sort typically requires additional memory to hold the sub-arrays during the merging process. This may impact its space complexity, especially for large datasets.
Example 2 - Merge Sort for Sorting Strings:
#include <iostream>
#include <vector>
#include <string>
void merge(std::vector<std::string>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary vectors to hold the two halves
std::vector<std::string> leftHalf(n1);
std::vector<std::string> rightHalf(n2);
// Copy data to temporary vectors leftHalf[] and rightHalf[]
for (int i = 0; i < n1; i++) {
leftHalf[i] = arr[left + i];
}
for (int i = 0; i < n2; i++) {
rightHalf[i] = arr[mid + 1 + i];
}
// Merge the two halves back into arr[]
int i = 0; // Initial index of the first subvector
int j = 0; // Initial index of the second subvector
int k = left; // Initial index of the merged vector
while (i < n1 && j < n2) {
if (leftHalf[i] <= rightHalf[j]) {
arr[k] = leftHalf[i];
i++;
} else {
arr[k] = rightHalf[j];
j++;
}
k++;
}
// Copy the remaining elements of leftHalf[], if any
while (i < n1) {
arr[k] = leftHalf[i];
i++;
k++;
}
// Copy the remaining elements of rightHalf[], if any
while (j < n2) {
arr[k] = rightHalf[j];
j++;
k++;
}
}
void mergeSort(std::vector<std::string>& arr, int left, int right) {
if (left < right) {
// Find the middle point
int mid = left + (right - left) / 2;
// Recursively sort the first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
int main() {
std::vector<std::string> strings = {"apple", "banana", "cherry", "date", "fig", "grape"};
int stringsCount = strings.size();
std::cout << "Original list of strings: ";
for (int i = 0; i < stringsCount; i++) {
std::cout << strings[i] << " ";
}
mergeSort(strings, 0, stringsCount - 1);
std::cout << "\nSorted list of strings: ";
for (int i = 0; i < stringsCount; i++) {
std::cout << strings[i] << " ";
}
return 0;
}
Explanation:
Merge Sort for Sorting Strings:
Merge Sort is a comparison-based sorting algorithm that is well-suited for sorting strings. Here's how it works for sorting a list of strings:
- Divide: The list of strings is divided into two approximately equal halves. This is done recursively until each sub-list contains only one string.
- Conquer: The individual string elements are considered sorted as singletons. Then, pairs of sub-lists are merged together into larger sub-lists while maintaining their sorted order. This merging process continues recursively until the entire list is sorted.
- Merge: When merging two sub-lists, you compare the strings in the two lists. You start with the first element in each list and compare them lexicographically. The smaller of the two strings is selected and added to the merged list. This process continues for all elements in both lists, effectively merging them while keeping the sorted order.
- Repeat: Steps 1 to 3 are repeated for all levels of recursion until the entire list is sorted.
The key to Merge Sort's effectiveness with strings is its ability to perform lexicographic comparisons to determine the correct order of the strings. This makes it a stable and efficient sorting algorithm for a list of strings.
In practice, you may need to implement a custom comparison function to handle specific string comparison requirements (e.g., case-insensitive sorting). The same basic principles of the Merge Sort algorithm can be applied to sort a list of strings without the need for a detailed code implementation.
Applications:
Merge Sort is a versatile and efficient sorting algorithm that finds applications in various domains and scenarios due to its stability, predictable time complexity, and ease of implementation. Here are some common applications of Merge Sort:
- General-Purpose Sorting: Merge Sort is widely used as a general-purpose sorting algorithm for sorting a list or array of elements. It's often used in programming libraries and applications for sorting data efficiently.
- External Sorting: Merge Sort is particularly useful for sorting large datasets that do not fit entirely in memory. It's employed in external sorting algorithms to efficiently sort data stored on external storage devices like hard drives.
- Merge-Purge Deduplication: In data cleaning and data deduplication tasks, Merge Sort can be used to efficiently identify and remove duplicate records from large datasets.
- Inversion Count: Merge Sort can be used to count the number of inversions in an array. Inversions represent the number of pairs of elements that are out of order, which can be useful in various applications, such as detecting anomalies in data.
- Music and Video Playback: Merge Sort can be used in media players to manage and play playlists. It ensures that the tracks or videos play in the correct order.
- Geospatial Data Processing: Merge Sort is employed in geographic information systems (GIS) and geospatial data processing for efficiently sorting geographical data, such as coordinates or geographical boundaries.
- Parallel Processing: Merge Sort can be parallelized to take advantage of multi-core processors and distributed computing environments, making it suitable for sorting in parallel applications.
- Database Indexing: In database systems, Merge Sort is used to sort and manage data within database indexes, improving the efficiency of query processing.
- Network Routing: In computer networking, Merge Sort is used for routing decisions and route optimization in scenarios like routing packets through various network paths.
- File Merging: Merge Sort is employed to merge multiple sorted files or data streams efficiently, which is useful in file manipulation and data integration.
- Online Marketplaces: Online marketplaces use Merge Sort to display products in a sorted order, allowing users to filter and search for items more effectively.
- Genomic Sequencing: In bioinformatics, Merge Sort is used to sort and merge large sets of genomic data, which is crucial for analyzing and processing DNA sequences.
Advantages:
Merge Sort's predictable time complexity and stability make it a valuable tool in various applications, and it continues to be relevant in the world of computing and data processing. Its suitability for large datasets and its predictable performance make it a popular choice for sorting tasks in many domains.
- Stability: Merge Sort is a stable sorting algorithm. It preserves the relative order of equal elements in the sorted output. This is crucial in scenarios where maintaining the original order of equal elements is important, such as in databases or when sorting objects with multiple attributes.
- Predictable Performance: Merge Sort has a consistent and predictable time complexity of O(n log n), making it efficient for large datasets. It doesn't suffer from the worst-case time complexity scenarios that other sorting algorithms like Quick Sort may encounter.
- Efficiency for Large Datasets: Merge Sort performs well even when sorting large datasets that don't fit entirely in memory. Its divide-and-conquer approach allows it to handle external sorting efficiently, making it suitable for sorting data on secondary storage like hard drives.
- Parallelism: Merge Sort can be parallelized, taking advantage of multi-core processors or distributed computing environments. This parallel processing capability can significantly speed up the sorting process in modern computing systems.
- Robustness: Merge Sort performs consistently across various input data distributions. It doesn't exhibit performance degradation based on the initial order of elements, unlike some other sorting algorithms.
- Adaptability: Merge Sort can be adapted and extended for specialized use cases. For example, it can be modified to perform stable in-place sorting with a small memory overhead.
- External Sorting: Merge Sort is a fundamental component of external sorting algorithms, making it suitable for scenarios where the entire dataset doesn't fit in memory and must be processed from external storage.
- Simplicity: Merge Sort is conceptually simple and easier to implement compared to some other sorting algorithms. It is a good choice for educational purposes and for developers who want to understand sorting algorithms.
- Low Memory Usage: Although Merge Sort requires additional memory for the temporary storage of sub-arrays during the merging process, it can be implemented to minimize memory usage and is often more memory-efficient than other algorithms like Heap Sort or Quick Sort.
- Versatility: Merge Sort can be applied to a wide range of data types and data structures, making it suitable for sorting integers, strings, complex data structures, and more.
- Merge-Purge Operations: Merge Sort is employed in applications like data deduplication, where it helps identify and remove duplicate records efficiently.
Time Complexity:
The time complexity of an algorithm quantifies the amount of time it takes to run as a function of the size of the input data. In the case of Merge Sort, its time complexity is O (n log n) for the worst-case, average-case, and best-case scenarios. This is a significant advantage of Merge Sort because it guarantees consistent performance regardless of the initial order of the elements.
Here's a breakdown of why Merge Sort has a time complexity of O(n log n):
- Divide Step: The input array is recursively divided into halves until each sub-array contains only one element. This division takes O(log n) time, where "n" is the number of elements in the array.
- Merge Step: Merging the sorted sub-arrays also takes O(n) time. This is because, in the worst case, it may require comparing and moving each element from both sub-arrays into a single sorted array.
The divide-and-conquer approach splits the sorting problem into smaller sub-problems and merges them, and this logarithmic division combined with linear merging results in the O (n log n) time complexity.
Space Complexity:
The space complexity of an algorithm refers to the amount of additional memory it uses with respect to the size of the input. Merge Sort has a space complexity of O(n) because it typically requires additional memory to store temporary sub-arrays during the sorting process.
Here's why Merge Sort has a space complexity of O(n):
- Divide Step: During the division process, Merge Sort creates temporary sub-arrays to hold the divided segments of the original array. These temporary sub-arrays are typically the same size as the original array. Therefore, in the worst case, the space required for these temporary arrays is O(n).
- Merge Step: During the merging process, Merge Sort combines the sorted sub-arrays back into a single sorted array. However, this merging step does not increase the space complexity because it doesn't create new data structures. It merely combines the existing sub-arrays.
In summary, Merge Sort has a space complexity of O(n) due to the additional memory required for temporary sub-arrays. While this space overhead is a drawback for sorting large datasets, Merge Sort's stable and efficient performance makes it a popular choice in many applications, especially when memory constraints are not critical. Additionally, there are in-place variations of Merge Sort that reduce the space complexity, but they may be less straightforward to implement.
Disadvantages:
- Additional Memory Usage: Merge Sort typically requires additional memory to store temporary sub-arrays during the sorting process. This can be a significant drawback when working with large datasets. In contrast, some other sorting algorithms, like in-place sorts (e.g., Quick Sort), use less memory.
- Slower for Small Datasets: Merge Sort's divide-and-conquer nature makes it less efficient for small datasets. The overhead of splitting and merging may outweigh the benefits of the algorithm when dealing with only a few elements.
- Slightly Slower in Practice: While Merge Sort has a consistent time complexity of O (n log n), it tends to be slightly slower in practice compared to some other sorting algorithms, like Quick Sort. Quick Sort is often faster due to its better cache performance and reduced constant factors.
- Complexity of Implementing In-Place Variant: A traditional Merge Sort is not an in-place sorting algorithm, which means it requires additional memory for the temporary sub-arrays. Implementing an in-place version of Merge Sort can be more complex and less intuitive.
- Slower with Linked Lists: Merge Sort is not as efficient when applied to linked lists. Merging linked lists can involve more pointer manipulation, making it slower than other sorting algorithms specifically designed for linked structures.
- Not Adaptive: Merge Sort's performance is not adaptive to the initial order of the elements. It always divides the array into two halves, making it less suitable for nearly sorted data. Some other algorithms, like Insertion Sort, adapt well to partially sorted data.
- Not Ideal for Small Arrays: Merge Sort may not be the best choice for sorting very small arrays or lists due to its overhead in function calls and memory usage. Smaller datasets are often better sorted using simpler algorithms like Insertion Sort or Selection Sort.
Takeaways:
- Merge sort algorithm is commonly used and the intuition and implementation behind the algorithm is rather straightforward in comparison to other sorting algorithms. This article includes the implementation step of the merge sort algorithm in Python.
- You should also know that the time complexity of the merge sort method's execution time in different situations, remains the same for best, worst, and average scenarios. It is recommended that merge sort algorithm is applied in the following scenarios:
- When dealing with larger sets of data, use the merge sort algorithm. Merge sort performs poorly on small arrays when compared to other sorting algorithms.
- Elements within a linked list have a reference to the next element within the list. This means that within the merge sort algorithm operation, the pointers are modifiable, making the comparison and insertion of elements have a constant time and space complexity.
- Have some form of certainty that the array is unsorted. Merge sort will execute its operations even on sorted arrays, a waste of computing resources.
- Use merge sort when there is a consideration for the stability of data. Stable sorting involves maintaining the order of identical values within an array. When compared with the unsorted data input, the order of identical values throughout an array in a stable sort is kept in the same position in the sorted output.