3. (25 points) 3.1 Given 2n numbers, compute the number of possible ways to divide them into two sorted lists, each with n numbers. 3.2 Show that any algorithm that correctly merges two sorted lists performs at least 2no(n) comparisons. 3.3 Show that if two elements are consecutive in the sorted order and from different lists, they must be compared during the merge. 3.4 Show the lower bound is 2n1 comparisons for merging two sorted lists