Identify a problem that can efficiently be solved with merge sort. Implement the merge sort...

 

Transcribed Image Text:

• 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. 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)). • 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). Here is the example output of the program: Scores BEFORE sorting with merge sort: 66.70 53.80, 45.30, 85.67, 23.30 90.98, 46.50, 9.00, 74.87, 68.90, 84.00 82.00, 36.00, 19.98, 42.00, 58.30, 31.00. 40.00, 76.00, 86.0 0, 97.30, 20.98, 80.00, 54.98, 27.00, 45.98, 93.00, 82.00, 69.00, 89 .00 28.98 Scores AFTER sorting with merge sort: 9.00, 19.98, 20.98, 23.30, 27.00, 28.98, 31.00, 36.00, 40.00, 42.00, 45.30, 45.98, 46.50, 53.80, 54.98, 58.30, 66.70, 68.90, 69.00, 74.8 7, 76.00, 80.00, 82.00, 82.00, 84.00, 85.67, 86.00, 89.00, 90.98, 93 .00 97.30 Don't forget the summary of the time complexity of the merge sort algorithm. An example of this is not included here. • 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. 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)). • 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). Here is the example output of the program: Scores BEFORE sorting with merge sort: 66.70 53.80, 45.30, 85.67, 23.30 90.98, 46.50, 9.00, 74.87, 68.90, 84.00 82.00, 36.00, 19.98, 42.00, 58.30, 31.00. 40.00, 76.00, 86.0 0, 97.30, 20.98, 80.00, 54.98, 27.00, 45.98, 93.00, 82.00, 69.00, 89 .00 28.98 Scores AFTER sorting with merge sort: 9.00, 19.98, 20.98, 23.30, 27.00, 28.98, 31.00, 36.00, 40.00, 42.00, 45.30, 45.98, 46.50, 53.80, 54.98, 58.30, 66.70, 68.90, 69.00, 74.8 7, 76.00, 80.00, 82.00, 82.00, 84.00, 85.67, 86.00, 89.00, 90.98, 93 .00 97.30 Don't forget the summary of the time complexity of the merge sort algorithm. An example of this is not included here.

Answer rating: 100% (QA)

The problem that is being handled using Merge sort is Inversion count in Array Problem Definition How far or close an array is to being sorted is indi... View the full answer