Due: Friday, Feb 6th in class Late assignments will be penalized 20% per day.

Book Questions from Introduction to Algorithms - 3rd ed.

2.3-5 (recursively)

3-2 (with brief justifications for each row)

4-1 (b,c,d,e), 4-3 (f)

Merge sort implementation.

Hints:

2.3-5 - Be sure to give a recursive algorithm and the corresponding recursive equation. Then solve the equation via Master theorem.

3-2 - Refer to the properties of logs and exponentials in section 3.2, particularly eq. 3.15, 3.18, and the following properties

image

i.e. polynomials are bounded by exponentials and logarithms are bounded by polynomials.

4-1 - Use the Master theorem by identifying the appropriate cases.

4-3 - Construct a recursion tree to obtain a guess at the runtime of O(n). Verify your guess using substitution.

Implementation

A skeleton project is provided in CS360_Sorter_Merge.zip. The zip file contains both a Visual Studio 2013 project and a Linux/OSX makefile to compile the code. Sorter.cpp contains both utility functions as well as empty sort function stubs - you should not need to modify main() or any of the utility functions.

Your Task

Implement the sort algorithm as given in the pseudocode below for merge sort. Insert counter increment statements (note: a count global variable is provided), into each sorting function for each executable line of pseudocode (e.g. count all three lines required to implement a swap as a single operation). Use this counter to empirically measure the runtime of each sort. Only increment the counter for statements within the sorting functions, i.e. do not include any initialization overhead incurred in main() or the utility functions. Note that count is reset prior to each sort call but the results are stored in a 2D array counter which is used to display a table of all results once all the sorts and runs have completed.

Generate runs for 13 input sizes using increasing powers of 2 from 24 = 16 to 216 = 65536.

The #define NUM_AVG sets the number of data sets of each size to generate in order to compute an average runtime for each size. This value should be set to a reasonable number, e.g. 10, to give a good approximation of the average runtime of each sort. Note that the larger the value that is chosen, the longer the program will take to run.

You should generate tables for two different input ranges

Once the data for all input sizes and element ranges have been generated, make a meaningful plot (e.g. using Excel) of the data showing important characteristics. In particular:

Hint: To plot cn lg n, consider making another column in the spreadsheet that computes the values for each empirical input size n and then plot that data as connected points without showing the individual data points.

Merge Sort

MERGE-SORT(A,p,r)
1  if p < r
2     q = (p+r)/2
3     MERGE-SORT(A,p,q)
4     MERGE-SORT(A,q+1,r)
5     MERGE(A,p,q,r)

MERGE(A,p,q,r)
1  n1 = q - p + 1
2  n2 = r - q
3  let L[1..n1+1] and R[1..n2+1] be new arrays
4  for i = 1 to n1
5     L[i] = A[p+i-1]
6  for j = 1 to n2
7     R[j] = A[q+j]
8  L[n1+1] = INF
9  R[n1+1] = INF
10 i = 1
11 j = 1
12 for k = p to r
13    if L[i] <= R[j]
14       A[k] = L[i]
15       i = i + 1
16    else
17       A[k] = R[j]
18       j = j + 1