CS3353

Programming assignment - may be written in C, C++, or Java

1. Implement a merge sort and a bucket sort as defined in class. (2 programs)

Input:

list of integers (size at least 100000 integers)

Output:

1. Print the sorted list within the selected range for each algorithm, respectively

2. A file with a plot for merge sort and bucket sort with both be on the same graph for comparison purpose (use a spreadsheet)

e.g., sort the first 1000 and measure the time, then refresh and sort the first 2000 and measure the time, and so on so forth):

list after sorting with interval of 1000 integers (execution time in nano seconds)

3. A plot for the asymptotic time for merge sort and bucket sort overlapped in the same graph in #2 for comparison purpose.

Expected output on graph:

X axis: input size() 1000, 2000, 3000,.100000;

Y axis: execution time in nano seconds

Expected output on CSX:

Input: a sequence of Integers read from file

Consider for example, input is 16, 17, 9, 8, 6 , 5, 4 -> Once sorted, output will be 4,5,6,9,16,17

Your program should prompt Enter the range

If the grader selects range (1,3)

Output to be displayed on console will be 5,6,9

What to submit:

A source code for each algorithm (merge sort and bucket sort)

A plot file (Excel)

A command line user interface has to be provided as follows:

Enter your input file name:

*Provide a README file with specific instructions for compilation and execution for the grader to follow, and any notes you want to add such as how you handle overflow, etc.