Lecture 351:- Recursive Merge Sort

Here's the C++ implementation of Recursive Merge Sort:

cppCopy code

#include <iostream> #include <vector> using namespace std; // Function to merge two sorted arrays into a single sorted array void merge(vector<int>& arr, int left, int mid, int right) {    vector<int> temp(right - left + 1);    int i = left, j = mid + 1, k = 0;    while (i <= mid && j <= right) {        if (arr[i] <= arr[j])            temp[k++] = arr[i++];        else            temp[k++] = arr[j++];    }    while (i <= mid)        temp[k++] = arr[i++];    while (j <= right)        temp[k++] = arr[j++];    for (int p = 0; p < k; p++)        arr[left + p] = temp[p]; } // Recursive Merge Sort function void recursiveMergeSort(vector<int>& arr, int left, int right) {    if (left < right) {        int mid = left + (right - left) / 2;        // Sort the left and right halves recursively        recursiveMergeSort(arr, left, mid);        recursiveMergeSort(arr, mid + 1, right);        // Merge the two sorted halves        merge(arr, left, mid, right);    } } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};    cout << "Original Array: ";    display(arr);    recursiveMergeSort(arr, 0, arr.size() - 1);    cout << "Sorted Array: ";    display(arr);    return 0; }

In this implementation, the merge function is used to merge two sorted sub-arrays. The recursiveMergeSort function performs the Recursive Merge Sort by dividing the array into two halves and recursively sorting each half. Finally, it merges the two sorted halves.

When you run this code, it will display the original array and then the sorted array after applying the Recursive Merge Sort algorithm.