a) Consider using mergesort to sort a sequence of points in the plane, according to their x- coordinate, breaking ties in the merge step by picking the point in the left list. Prove that the sorted sequence preserves the order of the y-coordinates of points whose x- coordinates are equal. For example, mergesort on the sequence (2, 2), (1, 1), (2, 1), (1, 2) yields (1, 1), (1, 2), (2, 2), (2, 1). (Hint: Use a proof by induction.)

(b) A sequence of points (x1, y1), . . . , (xn, yn) in the plane is nicely sorted if, for all i {1, . . . , n 1}, either (i) xi < xi+1 or (ii) xi = xi+1 and yi yi+1. For example, (1, 2), (2, 1), (3, 0), (3, 1) is nicely sorted but (2, 1), (1, 2), (3, 1), (3, 0) is not (the first/last two points violate conditions (i)/(ii)). Give a simple algorithm to nicely sort a sequence of points in the plane.