2. Here is a sorting algorithm that I like to use. Given an unsorted list of size n, let Xx represent the data in location k of the unsorted list. Compare xi to X2 and switch if necessary so that they are in sorted order, smallest first. Compare Xn-1 and Xn and switch if necessary so that they are in sorted order, smallest first. Compare x3 with its left neighbors, switching if necessary so that the 3 first entries are sorted. Compare Xn-2 with its right neighbors, switching if necessary so that the last 3 entries are sorted. Continue in this manner with X4, Xn-3, X5, Xn-4...until you have sorted element X1/2. I now have two sorted lists, each of size n/2. Merge the two sorted lists to create one sorted list of size n. Compare the data in location 1 with the data in location n/2 selecting the smallest. Compare the larger of those two elements with the next element in the opposing list and select the smallest and so on. a) State the running time of this algorithm using the most accurate informative) order notation possible. b) Prove the worst-case I running time of this algorithm. Full credit is given for the most clear and concise proofs