Consider an initial distribution where x1 and xn have the same number K = (N − n + 2)/2 of data items, while all other entities have just a single data item. Augment protocol OddEven-MergeSort so as to perform an invariant sort when π =
1, 2, . . . , n. Show the corresponding sorting diagram. How many additional simple merge operations are needed? How many operations does your solution perform? Determine the time and message costs of your solution.