Question

Lab Overview:

In this lab, you will work with merge sort.

Objectives:

• Identify a problem that can efficiently be solved with merge sort.
• Implement the merge sort algorithm
• Determine and summarize the algorithmic run-time of the merge sort algorithm.

Specifications:

As you saw from your readings and exercises, Merge Sort is based upon the idea of divide-and-conquer. If implemented correctly, your merge sort algorithm should have a time complexity of O(n*log(n)).

Your task for this lab is to write a program that utilizes the merge sort algorithm. You can identify any problem that you wish (or make up a hypothetical problem), but the sorting algorithm that you must use to sort the data is merge sort. It is up to you ( your choice ) as to how you want to utilize merge sort within your program.

Once you have finished, write a small summary to describe the algorithmic time complexity of merge sort.

Example:

(If you're having a hard time coming up with your own idea, then you may use my example problem below.)

Mrs. Wh has 31 students take an exam. She is presented with 31 decimal values which represent exam scores. The scores are stored in an array. She would like you to write a program which will sort those scores into ascending order (using merge sort).

Answer 1

ANSWER:-

#include <iostream>
using namespace std;
//merge the two half into a sorted data.
void merge(int *arr, int l, int h, int mid){
   int i, j, k, temp_arr[h-l+1];
   i = l;
   k = 0;
   j = mid + 1;

   // Merge the two parts into temp[].
   while (i <= mid && j <= h)
   {
       if (arr[i] < arr[j])
       {
           temp_arr[k] = arr[i];
           k++;i++;
       }
       else
       {
           temp_arr[k] = arr[j];
           k++;j++;
       }
   }
   while (i <= mid)
   {
       temp_arr[k] = arr[i];
       k++;i++;
   }
   while (j <= h)
   {
       temp_arr[k] = arr[j];
       k++;j++;
   }
   for (i = l; i <= h; i++)
   {
       arr[i] = temp_arr[i-l];
   }
}

// divide array into two part
void mergeSort(int *arr, int l, int h)
{
   int mid;
   if (l < h){
       mid=(l+h)/2;
       mergeSort(arr,l,mid);
       mergeSort(arr,mid+1,h);
       merge(arr,l,h,mid);
   }
}

int main()
{
   int len,i;
   cout<<"\nEnter no of scores: ";
   cin>>len;

   int a[len];
   for(i=0;i<len;i++)
   {
       cout<<"Enter element: ";
       cin>>a[i];
   }

   mergeSort(a, 0, len-1);
   cout<<"Sorted Data: "<<endl;
   for (i = 0; i < len; i++)
cout<<a[i]<<endl;

   return 0;
}

SUMMARY OF TIME COMPLEXITY: - Time complexity of merge sort is O(n* logn)

NOTE: - I have given random numbers. You can test with your values. It works well. If you have any doubts please comment below. THANK YOU!!! Please like my answer.

OUTPUT:-