C++

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 a test. She is presented with 31 decimal values which represent test 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).

Here is the example output of the program:dDon't forget the summary of the time complexity of the merge sort algorithm. An example of this is not included here.