Introduction

In this assignment, you'll implement two sorting algorithms that we've studied in class, and measure the performance of the algorithms:

Insertion Sort

Merge Sort

You'll write code to implement these two algorithms (don't use library routines for sorting). You'll measure the performance of these two algorithms on various size arrays, and compare the execution times of the two algorithms as the input size increases.

For smaller inputs, you'll find that Insertion Sort is faster. You should determine the smallest of the specified input sizes at which Merge Sort becomes faster than Insertion Sort. This size will vary depending on your individual implementation.

Measuring Execution Time

Measuring the timing of a single execution of an algorithm is usually imprecise, since the run time (especially for small inputs) may be on the order of the precision of the system timer. For performance measurement, we'll normally run an algorithm many times and then compute the average time for each execution.

Sorting algorithms reorder the original data, which may change the run time on subsequent executions (as we've seen with insertion sort).

For this assignment, your sort routines should copy a sub-range of the input array into an output array before sorting. The input array should not be modified. It will be reused for multiple calls to the sorting routine.

Copying an Array

Java

In Java, use the ArrayList type to store your arrays. You can create a copy of a portion of an ArrayList simply by passing a sub-list of it to the constructor of a new ArrayList. For example:

 // Create a new array ArrayList a1 = new ArrayList(); // ... put values in array here // Create new ArrayList from first 100 items of a1 ArrayList a2 = new ArrayList(a1.subList(0, 100));

Program Components

You'll need the following pieces to implement this assignment. An overall description of the task to perform is in the next section. You may also define any additional functions that you need (for example, Merge for MergeSort).

AlphaSorted: implement a function that takes as an argument an ArrayList (Java) or vector (C++) of strings. The function should verify that the array is sorted by checking that each element precedes or is equal to the following element. Return true if the array is correctly sorted, false otherwise. The array must not be modified by this function.

InsertionSort: implement a function that takes as arguments an input array to be sorted and a length n. The function should copy the first nelements of the input array to a new output array containing only those n elements, and then use the Insertion Sort algorithm as described in class to sort the output array. The input array must not be modified. The function should return the new output array.

MergeSort: implement a function as above for InsertionSort, but using the Merge Sort algorithm instead. You'll need an outer, non-recursive MergeSortSetup function that copies the array sub-range and then calls a recursive function, MergeSort, to sort the output array. The recursive function should not make another copy of the entire array. In your Merge routine, there is no such thing as infinity for strings, so you'll need to modify Merge to check for the end of the L and R arrays in some other way. You may not assume that you can choose a string which will be greater than all the strings in the input.

Code to measure CPU time.

Your Task

Create the input array by reading strings from the file specified by the first program command line argument into an ArrayList (Java).

Your program should loop with variable n, where n is successively set to each power of two from 8 (23) to 8192 (213) inclusive (12 different values of n). Use a for loop and just multiply the index by 2 every time through the loop to iterate over n.

For each value of n:

Calculate number of timing iterations iter = max(4, 8192/n) for Java. While debugging, you may wish to just set iter to 1; once everything is working correctly, use the full calculation to get more accurate timing.

For each value of n, call InsertionSort iter times to sort the first n items in the input array, using CpuTimer to calculate the total time for all the iterations. Divide this time by iter to get the average time for each call to InsertionSort.After computing the timing, check all of the following:

AlphaSorted is false for the input array.

AlphaSorted is true for the final output array.

Abort the program with a message if any of the above conditions are not met.

Repeat the same procedure you used for InsertionSort (using a separate timer) for MergeSortSetup.

Output

For each iteration of the loop, print to standard output the sub-array size n, and the average times for InsertionSort and MergeSort. Compute the average times in double precision, but convert to single precision (float) for output to avoid extraneous digits. Your output must follow the sample output format below.

Sample Output

My results using Java on a 2.2 GHz Intel Core i7 processor are shown below; your times will differ. My total run time was 77 sec. If your run time in Java is significantly lower, make sure that you have specified the -Xint parameter to the JVM (see comments in CpuTIme.java). If you don't specify this parameter, your run time will be faster, but the results may be invalid due to "Just In Time" (JIT) compilation.

Avg. times for n = 8: Insertion Sort 2.2018554E-5 sec., Merge Sort 6.153223E-5 sec. Avg. times for n = 16: Insertion Sort 4.778125E-5 sec., Merge Sort 1.4660938E-4 sec. Avg. times for n = 32: Insertion Sort 2.0401173E-4 sec., Merge Sort 3.4345314E-4 sec. Avg. times for n = 64: Insertion Sort 9.598672E-4 sec., Merge Sort 7.6977344E-4 sec. Avg. times for n = 128: Insertion Sort 0.003998578 sec., Merge Sort 0.0016862656 sec. Avg. times for n = 256: Insertion Sort 0.0112554375 sec., Merge Sort 0.0037691563 sec. Avg. times for n = 512: Insertion Sort 0.045366876 sec., Merge Sort 0.008297 sec. Avg. times for n = 1024: Insertion Sort 0.20330137 sec., Merge Sort 0.018066 sec. Avg. times for n = 2048: Insertion Sort 0.83871025 sec., Merge Sort 0.0383705 sec. Avg. times for n = 4096: Insertion Sort 3.3997889 sec., Merge Sort 0.0791235 sec. Avg. times for n = 8192: Insertion Sort 13.6423435 sec., Merge Sort 0.1741685 sec.