Algorithm Sorting on Structured Lists

Although any comparison-based sorting algorithm must take time (n log n), in some cases it is possible to obtain faster algorithms if we assume more about the structure of the input list. For each of the following assumptions, give the best lower bound on the number of comparisons for sorting you can using a decision tree argument. Because of the assumptions on the structure of the list, you might get a better lower bound than (n log n). If this is the case, give an algorithm to sort the list that matches the lower bound (a) (5 points) The input list is k-sorted, that is, the first k elements are each less than the next k elements, which are each less than the next k elements, and so on. More specifically, a(i-1)k+j S aike for alll aikte a (b) (5 points) The input list is sorted if you look at only the even positions. That is, the second element is less than the fourth element, which is less than the sixth element, and in general a2i-aDj f i-j. However, the odd positions can be anything. You can assume without proof that n -2n (c) (5 points) The input list is sorted if you look at only the even positions. That is, the second element is less than the fourth element, which is less than the sixth element, and in general a2i ^ a2j if i aikte a (b) (5 points) The input list is sorted if you look at only the even positions. That is, the second element is less than the fourth element, which is less than the sixth element, and in general a2i-aDj f i-j. However, the odd positions can be anything. You can assume without proof that n -2n (c) (5 points) The input list is sorted if you look at only the even positions. That is, the second element is less than the fourth element, which is less than the sixth element, and in general a2i ^ a2j if i