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:
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
    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
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.

Problem 0 (assessment: self_______ final_______)

Prove that

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

is an invariant for both loops in the above algorithm

Problem 1 (assessment: self_______ final_______)

Use the above invariant to prove that we never overwrite a value in the range A[i2..j2], so the fear of losing or corrupting data is unfounded.