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

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

## C++ Sorting: Exercise-10 with Solution

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: