Exercise 1. (25 points) Given is an array A = A [1], A [2],. . . , A [n] containing n different integers, with n 2 even. The array consists of n/2 consecutive sub-rows, each sub-row containing 2 elements. It is also given that both values from a partial row are always greater than all values before, and less than all values after. We want to sort the row in ascending order. An example of such a sequence with n = 10: 3, 6, 1, 4, 9, 8, 14, 11, 17, 20.

a. (6 points) How many comparisons does Quicksort make in rows as described above worst case for general (even) n? We look at the version of Quicksort where we always choose the first element of the row concerned as the pivot.

b. (10 points) Show using a decision tree argument that any sorting algorithm based on array comparisons for these input rows must do at least n//2 comparisons in the worst case. Formulate your evidence carefully.

c. (6 points) Also by looking at the number of inversions, you can prove a lower bound of n/2 for this problem. Prove: any sort algorithm that is based on array comparisons and that cancels at most one inversion per array comparison, does in the worst case for the input rows viewed here at least n/2 of these comparisons. Your proof must at least contain what an inversion is, how many inversions the rows viewed have at most and what the relationship is between inversions and the number of comparisons in the worst case.