I got answer from someone about Q1 and I have one more question ---> Q2. Sort the above array using merge sort technique (paper and pencil technique).

Q 1.

Write the Merge sort function that accepts an array and sorts the array.

Test your code with the following numbers. 15, 22, 8, 25, 3, 44, 1, 6.

Q2.

Sort the above array using merge sort technique (paper and pencil technique).

Below description and codes are the answer about Q1.

Problem Description

1. Merge-sort is based on an algorithmic design pattern called divide-and-conquer. 2. It forms tree structure. 3. The height of the tree will be log(n). 4. we merge n element at every level of the tree. 5. The time complexity of this algorithm is O(n*log(n)).

Problem Solution

1. Split the data into two equal half until we get at most one element in both half. 2. Merge Both into one making sure the resulting sequence is sorted. 3. Recursively split them and merge on the basis of constraint given in step 1. 4. Display the result. 5. Exit.

Program Code

#include using namespace std; // A function to merge the two half into a sorted data. void Merge(int *a, int low, int high, int mid) { // We have low to mid and mid+1 to high already sorted. int i, j, k, temp[high-low+1]; i = low; k = 0; j = mid + 1; // Merge the two parts into temp[]. while (i <= mid && j <= high) { if (a[i] < a[j]) { temp[k] = a[i]; k++; i++; } else { temp[k] = a[j]; k++; j++; } } // Insert all the remaining values from i to mid into temp[]. while (i <= mid) { temp[k] = a[i]; k++; i++; } // Insert all the remaining values from j to high into temp[]. while (j <= high) { temp[k] = a[j]; k++; j++; } // Assign sorted data stored in temp[] to a[]. for (i = low; i <= high; i++) { a[i] = temp[i-low]; } } // A function to split array into two parts. void MergeSort(int *a, int low, int high) { int mid; if (low < high) { mid=(low+high)/2; // Split the data into two half. MergeSort(a, low, mid); MergeSort(a, mid+1, high); // Merge them to get sorted output. Merge(a, low, high, mid); } } int main() { int n, i; cout<<" Enter the number of data element to be sorted: "; cin>>n; int arr[n]; for(i = 0; i < n; i++) { cout<<"Enter element "< Sorted Data "; for (i = 0; i < n; i++) cout<<"->"<

Explanation

1. Take input of data. 2. Call MergeSort() function. 3. Recursively split the array into two equal parts. 4. Split them until we get at most one element in both half. 5. Combine the result by invoking Merge(). 6. It combines the individually sorted data from low to mid and mid+1 to high. 7. Return to main and display the result. 8. Exit.

Output:- Enter the number of data element to be sorted: 8

Enter element 1: 15

Enter element 2: 22

Enter element 3: 8

Enter element 4: 25

Enter element 5: 3

Enter element 6: 44

Enter element 7: 1

Enter element 8: 6

Sorted Data ->1->3->6->8->15->22->25->44