3. Consider the following sorting algorithm that takes a list of integers as an input and outputs a sorted list of those elements. (note, the MERGE subroutine is the same algorithm as the previous problem.) QueueSort(a1,..., an) 1. Initialize a queue Q of lists so that each element of the input is in a list all by itself. 2. Q=([a1], [2], ..., [an]) 3. while Q2: 4. 5. dequeue the first two lists from Q and MERGE the two lists together. enqueue the result into Q. Example: Sort the list: (10,8,3,2,8,7,6) ([10], [8], [3], [2], [8], [7], [6]) MERGE([10], [8]) ([3], [2], [8], [7], [6]) ([3], [2], [8], [7], [6]) [8, 10] MERGE([3], [2]) ([8], [7], [6], [8, 10]) (3,2,8,7,6, [8, 10]) ([8], [7], [6], [8, 10]) + [2,3] ([8], [7], [6], [8, 10], [2,3]) MERGE([8], [7]) ([6], [8, 10], [2,3]) ([6], [8, 10], [2,3])+ [7,8] ([6], [8, 10], [2,3], [7,8]) MERGE([6], [8, 10]) ([2,3], [7,8]) ([2, 3], [7, 8]) [6, 8, 10] ([2, 3], [7, 8], [6, 8, 10]) MERGE([2,3], [7,8]) ([6, 8, 10]) ([6, 8, 10])[2, 3, 7, 8] ([6, 8, 10], [2, 3, 7, 8]) MERGE([6, 8, 10], [2, 3, 7, 8])+() ()[2, 3, 6, 7, 8, 8, 10] ([2, 3, 6, 7, 8, 8, 10]) Consider the loop invariant: After each iteration, every list in Q is sorted. (a) (8 points) Prove this loop invariant using induction. (Note: you can assume the correctness of MERGE in your argument.) (b) (4 points) Use the loop invariant to show that the algorithm QueueSort is correct. (c) (4 points) Use the runtime method we learned in class to show that this algorithm runs in O(n) time. (Note: you can assume that Merge([a1,..., ak], [b1,..., be]) has a runtime of O(k + l).) (d) (2 points) Then give a brief argument about whether or not O(n) is a tight bound.