Comparing Sorting Methods

Implement methods to do a bubble sort and a non-recursive merge sort on a long array, using the following starter code.

The starter code contains a method called MergeSortNonRec(long[] a). This is where you should put your code that implements a non-recursive version of merge sort. The recursive version of a merge sort and the non-recursive version are very similar -- except that in a non-recursive mergesort, one starts with a pass of 1-by-1 merges (merge every two adjacent elements, subarrays of size 1, to make subarrays of size 2), then one makes a pass of 2-by-2 merges (merge subarrays of size 2 to make subarrays of size 4), then 4-by-4 merges, and so forth, until we do a merge that encompasses the whole array.

Note: you may find it advantageous to call the merge() method that is already implemented in the starter code to accomplish the merging, although you may implement your own version of the merge() method if you wish.

Similar to the algorithm for a recursive merge sort, you will need to create an auxiliary array in order to call this merge() method. In addition, you will need to correctly calculate the lo, mid, and hi indices and pass them to the merge() method. You may assume that the size of the input is always a power of 2. This will greatly reduce the complexity of the solution. If your implementation is correct, it should in fact run slightly faster than the recursive mergesort, because there is no overhead of recursive method calls.

When you are done implementing the bubble sort and non-recursive merge sort methods, compare the average performance of the 5 different sorting algorithms addressed in your code: bubble sort, selection sort, insertion sort, recursive merge sort, and non-recursive merge sort. (Note: the selection sort, insertion sort, and recursive mergesort are provided in the starter code.)

The code for running the comparisons for different input sizes are provided in the main method. For each algorithm, it tests different input sizes (the default is 15, which means it tests the first 15 powers of 2). The data is randomly generated. The main method performs each test multiple times (the default is 5 times) in order to get an average running time. Afterwards, it will print the results as a table: each row reports the input size (N), and the average running time for each algorithm in milliseconds. When you have familiarized yourself with the code in the main method and completely understand how the experiments are carried out, run the program and examine the table to compare the run times for the various algorithms. You can increase the value of the max variable if you wish, but be aware that bubble sort will take quite a bit of time.

To help, notice that the starter code checks after each sorting algorithm whether the sorting result is correct. If your sorting implementation produces incorrect sorting result, a message 'The sorting is INCORRECT! ' will be printed out. So watch for such messages.

After the program prints out the table, plot the results in a graph. You can use Google SpreadSheet, Microsoft Excel, OpenOffice Calc, or other tools to this end. Does what you see agree with the Big-O analysis of each of these algorithms average running times?