Merge Sort Recursive in C++
A sorting technique known as merge sort divides a large array into smaller subarrays sorts each subarray individually and then merges the sorted subarrays back together to create the final sorted array. That technique is called divide and conquer.
In other words, the merge sort procedure involves splitting the array, sorting each half, and then joining the sorted halves. Up till the full array is sorted, this procedure is repeated.
In this tutorial, we will see a step-by-step explanation of the Merge Sort procedure with a recursive C++ implementation:
- Divide: The array into two halves, a left and a right half, as the initial step. Recursively, this division is carried out until each subarray contains just one element. This serves as the recursion's fundamental case.
- Conquer: After dividing, we concentrate on sorting each subarray separately. These arrays are already thought of as sorted because each subarray in the base case only contains one element.
- Merge: The merging process starts once the subarrays have been sorted. Combining two smaller sorted subarrays into one larger sorted array is the objective. In this way, the "Merge Sort" got its name.
Simple Steps to Perform Merge Sort
Step 1: Initial Array
Step 2: Divide into Subarrays
Step 3: Recursively Divide
Step 4: Sort and Merge Individual Elements
Step 5: Merge Subarrays
Step 6: Final Sorted Array
This demonstrates how the merge sort algorithm divides, sorts, and merges subarrays iteratively. To eventually produce a properly sorted array, each stage involves dividing arrays into smaller pieces, sorting them, and merging them.
Program:
#include <iostream>
#include <vector>
using namespace std;
//function to merge two subarrays and sort them
void partition(vector<int>& arr, int low, int mid, int high) {
// Calculate the sizes of the two subarrays
int size1 = mid-low + 1;
int size2 = high - mid;
// Create temporary arrays to hold the subarrays
vector<int> firstPart(size1);
vector<int> secondPart(size2);
// Copy data to temporary arrays
for (int i = 0; i < size1; i++)
firstPart[i] = arr[low + i];
for (int j = 0; j < size2; j++)
secondPart[j] = arr[mid + 1 + j];
// Merge the temporary arrays back into the original array
int i = 0; // Index for the first subarray
int j = 0; // Index for the second subarray
int k = low; // Index for the merged array
while (i < size1 && j < size2) {
if (firstPart[i] <= secondPart[j]) {
arr[k] = firstPart[i];
i++;
} else {
arr[k] = secondPart[j];
j++;
}
k++;
}
// Copy any remaining elements from the firstPart
while (i < size1) {
arr[k] = firstPart[i];
i++;
k++;
}
// Copy any remaining elements from the secondPart
while (j < size2) {
arr[k] = secondPart[j];
j++;
k++;
}
}
// Merge Sort function
void sorting(vector<int>& arr, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
// Recursively sort the two halves
sorting(arr, low, mid);
sorting(arr, mid + 1, high);
// Merge the sorted halves
partition(arr, low, mid, high);
}
}
int main() {
vector<int> arr = {12, 11, 13, 5, 6, 7};
cout << "Original array: ";
for (int num: arr)
cout << num << " ";
cout << endl;
// Call the sorting function to sort the array
sorting(arr, 0, arr.size() - 1);
cout << "Sorted array: ";
for (int num: arr)
cout << num << " ";
cout << endl;
return 0;
}
Output:
![Merge Sort Recursive in C++](https://static.tutorialandexample.com/cpp/merge-sort-recursive-in-cpp1.png)
Explanation:
1.Include Headers: Include the required input/output and vector header files.
2.Partition (Merging) Function:
- Create a partition function to combine two sorted subarrays.
- Make temporary arrays and determine the sizes of subarrays.
- Data is copied to temporary arrays and then combined with the original array.
3.The function of Merge Sort (Dividing and Sorting):
- Create the sorting function to divide and sort the array iteratively.
- Recursively sort the left and right halves after calculating the middle index.
- Utilize the partition function to combine the sorted halves.
4.In the Main function:
- Create an integer array.
- Print the initial array.
- To sort the array, use the sorting function.
- Display the sorted array.
The above example program demonstrates how the Merge Sort algorithm splits the array into smaller pieces sorts them repeatedly and then merges the parts back together to provide a sorted result. It illustrates how reliable and effective Merge Sort is by combining temporary arrays.
Merge Sort Complexity Analysis
Merge Sort is a recursive algorithm with an O(N log(N)) time complexity, which can be stated as the following recurrence relation.
T(n) = 2T(n/2) + θ(n)
1.Time Complexity: Sort has a time complexity of O(N log N) for all cases- worst, average, and best. Due to the array's continuous partition into two halves and the linear time required to merge the two halves, this complexity develops.
2.Space Complexity: Because each element is copied into a different auxiliary array during the merging operation, Merge Sort requires an auxiliary space of O(N). Therefore, N units of auxiliary space are required for the algorithm to run correctly.
3.Time Complexities:
- Best case: O (n log n)
- Average case: O (n log n).
- worst case: O (n log n)
Applications
Merge Sort is a sorting algorithm used to sort the given numbers. Large datasets can be efficiently and consistently sorted using merge sort, which is extensively utilized. It is ideal for various applications due to its predictable (N log N) time complexity.
- External sorting: When data cannot be stored entirely in memory and needs to be sorted from external storage, such as hard discs or tapes, merge sort is frequently utilized. It is the best option because of its divide-and-conquer method, which reduces disc I/O operations.
- Inversion count problem: Merge Sort can be used to resolve inversion count problems, in which the objective is to determine how far an array is from being sorted. The number of inversions in an array can be calculated during the merge process.
- Parallel computing: Merge sort is appropriate for parallel computing environments because it can be efficiently parallelized. The array can be split into smaller parts and sorted while doing so, and the sorted subarrays can then be combined.
Advantages of Merge Sort
- Stability: Merge By maintaining the initial order of identical elements in the input array as they appear in the sorted output, Sort displays stability.
- Guaranteed Worst-Case Performance: Merge Sort demonstrates consistent efficiency even when working with large data sets, ensuring dependable performance regardless of the input, where the time complexity in worst-case is O(n log n) where n is size.
- Inherent Parallelism: Merge Sort can be easily parallelized to use many processors or threads, increasing the speed at which it executes on contemporary parallel computing architectures.
- Merge Sort is ideal for Linked Lists: Merge Sort is a good choice for sorting linked lists because of its divide-and-conquer strategy. It effectively merges two linked lists and doesn't require random access to elements like other sorting algorithms.
- Memory Usage: Regardless of the input size, Merge Sort can be programmed to consume a fixed amount of memory. In circumstances where memory allocation is constrained, this may be useful.
- Flexibility: Merge Sort regularly outperforms competing algorithms on various input data types and distributions. It doesn't display the worst-case behaviour on some inputs that other algorithms might.
Drawbacks of Merge Sort
- Space complexity: Merge Space Complexity To handle the combined sub-arrays while navigating the sorting process, Sort needs additional RAM.
- Nature Out of Place: Merge Sort is not an in-place sorting algorithm; hence, additional memory must be allocated to store the sorted data. In situations where memory consumption optimization is crucial, this feature could be detrimental.
- Suboptimal for Small Datasets: When dealing with smaller datasets, the time complexity of Merge Sort may be higher than that of some other sorting algorithms, such as insertion sort. It may display comparably slower performance for small datasets.
- Merge Sort is Slower for Linked Lists: Merge Sort can still be used for linked lists, but doing so causes additional time for merging, making it less effective than other linked list algorithms like insertion sort.
Conclusion
In conclusion, Merge Sort is a powerful sorting algorithm with various useful characteristics. Large datasets can be efficiently sorted because of the stability, guaranteed worst-case performance of O(N log N), and intrinsic parallelizability. However, its need for additional memory and non-in-place nature could provide problems in contexts with limited memory. However, it excels in upholding stability and predictability because of its comparatively higher time complexity; there may be better options for sorting small datasets. Understanding the Merge Sort trade-offs and benefits is crucial to selecting the appropriate sorting strategy for your application.