A05

Due Date: Thursday, February 26
File(s) to be submitted: RunMerge.java
Sample Output: SampleOutput.html
Starter Files:

• MergeSort.java
• PrintTrace.java

Modified Merge Sort (More Recursive Sorting)

Summary

Download MergeSort and PrintTrace into a project. Create a new program, RunMerge, as a copy of MergeSort. Remove the method mergeSort and comment out the call to it.

Note: Do not delete the methods called merge. You will need those.

Add new methods to make RunMerge perform as shown in the sample output.

Details

For this assignment I want you to create new methods in RunMerge:

• runMerge(int[] arr): Takes an int[] and sorts it in the way shown in the sample output (and described more below). It is responsible for seeing that all the tracing messages get printed.
• findRuns(int[] arr): Returns an array showing where each run in the given array starts (and ends).
• showRuns(int[] arr, int[] runStarts): Reports how many runs have been found and shows each run, pausing after each one.
• reduceRuns(int[] runStarts): Returns a new array showing where the runs start (and end) after the sequence of merges has been carried out on the runs identified in runStarts.

About runMerge

You will call runMerge from main (in the place where mergeSort had been called).

• It will call findRuns to find where all the sorted subsequences of arr are.
• It will then loop until the number of runs is reduced to 1.
  • It will call showRuns to show those runs.
  • It will reduce the number of runs by merging consecutive runs. For each merge it will say which run numbers it is merging and show the result of that merger.

    Note: If there is an odd number of sorted sequences, then the last sequence will not get merged with any other sequence. Make sure you don't try to merge the last run with the one (that isn't!) after it!

    It pauses after each merge.
  • It will then call the method reduceRuns so that runStarts holds the new set of runs for the array.

    Note: You don't need to reduceRuns right away. You can replace it with a call to findRuns. However there is a better way to find the new starting/ending positions -- one that doesn't make any more comparisons on array elements. For full credit you will want to use this no-comparisons algorithm.

About findRuns

The method findRuns needs to create an array showing where each sorted subsequence begins. Suppose it is given the array:

463	552	796	357	229	307	332	990

In this array has three sorted subsequences:

463	552	796	...	...	...	...	...
...	...	...	357	...	...	...	...
...	...	...	...	229	307	332	990

The sequences start at locations 0, 3, and 4. The sequences end at 3, 4, and 8.

Remember: the standard way to represent start and end points in an array is to give the index of the first value in the sequence and the index of the first value after the sequence. Thus the first sequence is 0 to 3, the second is 3 to 4, and the last is 4 to 8 (where 8 is the length of the array).

It is (barely) possible that the array will be entirely out of order. For example:

400	300	200	100

would make findRuns return

0	1	2	3	4

That means the array you create for this method might need to be as long as arr.length + 1 elements. Since you don't know going in how many runs the given array is going to have, you need to create your array to be one space longer than the array you're given. For the 8-element array further up you would need to create an array of length 9 to hold the start/end positions needed. After you have filled in the start/end positions and thus know how many runs there are, use Array.copyOf to reduce the longer array you created down to one more than the number of runs.

About showRuns

The method showRuns needs to work its way thru the array returned by findRuns printing out the sorted subsequences of the array. Call

As in the sample output, each printed subsequence should be preceded by its number (the index in runStarts where its start is), and it should be followed by a pause.

About reduceRuns

The method reduceRuns needs to take an array of starting/ending points and return an array of revised starting/ending points. The revised array is the one that applies after one round of merging has been applied to the array. For example, merging the sequences 0 to 3 and 3 to 4 results in a sequence from 0 to 4.

Reminder: if there is an odd number of sorted subsequences then the last sequence won't get merged.

A longer example:

0	3	4	6	8	10	16

That should be replaced by

0	4	8	16

Other Requirements

Make sure your code is formatted properly.

Revise the class javadoc to update the description and add yourself as an author.

Update printIntroduction to print the introduction shown in the sample output, and put your name and A-number in the places reserved.

All new methods should have suitable javadoc comments.

Do not delete or change javadocs for pre-existing methods. (Except delete the javadoc for mergeSort along with the method.)