Given a positive integer sequence of size n. Please sort the sequence in ascending order via merge sort.
The following is the pseudocode for the algorithm:
MergeSort(arr[], l, r) If r > l 1. Find the middle point to divide the array into two halves: middle m = l+ (r-l)/2 2. Call mergeSort for first half: Call mergeSort(arr, l, m) 3. Call mergeSort for second half: Call mergeSort(arr, m+1, r) 4. Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)
Note: Repeated numbers may exist in the input sequence.
You may refer to the sample code template.cpp below:
#include <iostream>
using namespace std;
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int L[n1], R[n2];
// Copy data to temp arrays L[] and R[]
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[/**TODO**/];
// Merge the temp arrays back into arr[l..r]
// Initial index of first subarray
int i = 0;
// Initial index of second subarray
int j = 0;
// Initial index of merged subarray
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
/**TODO**/
}
k++;
}
// Copy the remaining elements of
// L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of
// R[], if there are any
while (j < n2) {
/**TODO**/
}
}
// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int arr[],int l,int r){
if(l>=r){
return;//returns recursively
}
int m = (l+r-1)/2;
mergeSort(/**TODO**/);
mergeSort(/**TODO**/);
merge(/**TODO**/);
}
void printArray(int A[], int size)
{
int i = 0;
for (i = 0; i < size; i++){
cout << A[i];
if(i != size-1) cout << " ";
}
cout << endl;
}
int main()
{
int arr_size = 0;
cin >> arr_size;
int arr[arr_size];
for(int i =0; i < arr_size; i++)
cin >> arr[i];
//cout << "Given array is \n";
//printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
//cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}
Print the sorted sequence.
Note:
Elements are separated by a single whitespace character.
There is no trailing whitespace in the last element.
You should append a newline character(\n) after the output.