Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

We might try to improve on the "merge" algorithm presented in
class and in the class notes (not the unit 2 notes) by creating
a copy of the first sorted range, but keeping the second sorted
range in-place in the array A. Here's how we might write that:
Describe help received: _________________________________________________________________

Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

The advantages are twofold: first, we save half of the copy costs both in time and memory, second, we get to drop the original version's third while loop altogether. On the other hand, it's not clear that we won't run into trouble by writing something into A in the first loop that overwrites an unplaced value from the left-half of the original range, thereby losing or corrupting data.Algorithm:merge(A,i,m,j) Inputs : array A, and indices i ≤ m ≤ j such that A[i..m] and A[(m+1)..j] are idividually in sorted order Outputs: array A is modified so that A[i..j] contains its original elements in sorted order A1 = new array copy of A[i..m] k = i, i1 = 0, j1 = m - i, i2 = m+1, j2 = j while i1 ≤ j1 and i2 ≤ j2 do ← keep adding the smaller of the initial elements of A1 & A[i2..j2] if A[i2] < A1[i1] A[k] = A[i2], i2 = i2 + 1, k = k + 1 else A[k] = A1[i1], i1 = i1 + 1, k = k + 1 while i1 ≤ j1 do ← add any remaining elements of A1 A[k] = A1[i1], i1 = i1 + 1, k = k + 1 free A1

$k + (j_1 - i_1 + 1) = i_2$

is an invariant for both loops in the above algorithm