C++ Merge sort Exercise: Sort a collection of integers using the Merge sort

Last update on December 20 2024 12:31:43 (UTC/GMT +8 hours)

Write a C++ program to sort a collection of integers using the Merge sort.

Sample Solution:

C++ Code :

#include<iostream>
using namespace std;

// Function to merge two subarrays into one sorted array
void Merge(int* arr, int p, int q, int r) {
    // Determine sizes of two subarrays
    int n1 = q - p + 1;
    int n2 = r - q;

    // Create temporary arrays to hold the subarrays
    int L[n1 + 1];
    int R[n2 + 1];

    // Copy elements to the temporary arrays
    for(int i = 0; i < n1; i++)
        L[i] = arr[p + i];
    for(int j = 0; j < n2; j++)
        R[j] = arr[q + 1 + j];

    int i = 0, j = 0, n = 0;

    // Merge the two subarrays into the original array in sorted order
    while(i != n1 && j != n2) {
        if(L[i] > R[j]) {
            arr[p + n] = R[j];
            j++;
        } else {
            arr[p + n] = L[i];
            i++;
        }
        n++;
    }

    // Copy any remaining elements from the right subarray, if any
    while(j != n2) {
        arr[p + n] = R[j];
        j++;
        n++;
    }

    // Copy any remaining elements from the left subarray, if any
    while(i != n1) {
        arr[p + n] = L[i];
        i++;
        n++;
    }
}

// Recursive function to perform Merge Sort
void Merge_Sort(int* arr, int p, int r) {
    // Base case: If there's more than one element
    if(r > p) {
        int q = (p + r) / 2; // Calculate middle index
        Merge_Sort(arr, p, q); // Sort left subarray
        Merge_Sort(arr, q + 1, r); // Sort right subarray
        Merge(arr, p, q, r); // Merge the sorted subarrays
    }
}

int main() {
    // Initializing an array of integers for sorting
    int a[] = {125, 0, 695, 3, -256, -5, 214, 44, 55};
    int len = 9;

    cout << "Original numbers:\n";
    // Displaying the original numbers in the array
    for(int i = 0; i < len; i++) {
        cout << a[i] << " ";
    }

    // Sorting the array using Merge Sort
    Merge_Sort(a, 0, len - 1);

    cout << "\nSorted numbers:\n";
    // Displaying the sorted numbers after Merge Sort
    for(int i = 0; i < len; i++) {
        cout << a[i] << " ";
    }

    return 0;
}

Sample Output:

Original numbers:
125 0 695 3 -256 -5 214 44 55 
Sorted numbers:
-256 -5 0 3 44 55 125 214 695

Flowchart:

C++ Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C++ program to sort an array of elements using the Insertion sort algorithm.
Next: Write a C++ program to sort a collection of integers using the Pancake sort.