1. An integer matrix is an n m array of integers; for example: A =

{ 3 10 4

1 1012 18

3 12 101

67 0 23

3 10 5 }

A row is a series of numbers from left to right and a column is the series from top to bottom. Here, we will modify merge sort to sort the rows of a matrix, with respect to their columns. For the above example, this yields: A =

{1 1012 18

3 12 101

3 10 4

3 10 5

67 0 23 }

(a) (15 pts) Write pseudocode for this modified version of merge sort (call it MatrixMergeSort)

(b) (20 pts) Prove the best- and worst-case complexity of MatrixMergeSort. For simplicity, assume that the matrices are square (i.e. they are n n matrices, in which the number of rows is equal to the number of columns).

(c) (5 pts) Assume that comparing two rows can be done in constant time ((1)). Is the worst-case complexity of MatrixMergeSort in this case better or worse than regular merge sort? Why?

(d) Extra credit (5 pts): Assume that we are guaranteed that each row of the matrix is pre-sorted (i.e, increasing from left to right). For the example above, we would have: A =

{3 4 10

18 1 1012

101 12 3

23 0 67

3 5 10 }

Does this guarantee change the worst-case complexity of MatrixMergeSort?