In this exercise we will develop an algorithm that is adaptive to one measure of presortedness. Remember that two elements x_i and x_j of the input sequence form an inversion if i < j and x_i > x_j, i.e., the two elements appear in the wrong order in the input. Intuitively, a sequence is nearly ordered if the elements of an inversion are close together. We dene the order of an inversion as the distance between the two elements of an inversion, i.e., the value j i, and we dene the inversion order of a sequence as the maximum order of all inversions. Note that the inversion order is zero if the data are properly sorted, the inversion order is one if all inversions are between neighbors in the sequence, and the inversion order is n 1 in the worst case (if there is an inversion between the rst and last element of the sequence).

1) Classical mergesort works as follows: If the sequence consists of a single element, we do nothing because a single element is already sorted. Otherwise, we split the sequence in the middle into a left and right half, recursively mergesort both halves, and then merge both sorted sequences in linear time into a single sorted sequence. Show that the runtime of mergesort on a set of n elements is O(nlogn) if the data are given as a doubly-linked list.

2) We now slightly modify the mergesort algorithm and call it adaptive mergesort. Instead of dividing the input sequence in the middle we do a modulo-2 split, i.e., we put all even-indexed elements into the left half and all odd-indexed elements into the right half. Furthermore, before recursively sorting each half we rst test whether such a sort is actually necessary, i.e., we rst test whether the sequence is already properly sorted. This can be done in linear time with a single scan over the data, in each step testing whether the element is not larger than the next one. If the input sequence is properly sorted, no recursion will happen and the runtime will be O(n). Show that there will also be no recursion if the inversion order of the input sequence is one.

3) Generalize the observation in part (b) and show that at most logp recursive steps can happen if the inversion order of the input sequence is p. Conclude that the runtime of adaptive mergeseort is O(nlogp), which is between O(n) if the input is already sorted and O(nlogn) in the worst case.