(Solved): (15 points) Consider the following sorting algorithm that takes a list of integers as an input and ...

(15 points) 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 an algorithm we will talk about on Tuesday. You can find it in the slides. All you need to know about MERGE is that it takes two sorted lists of integers and returns a sorted list of all the integers combined. If the size of the lists are $j$ and $k$, then the runtime of MERGE is $O(k+j)$.) QueueSort $\left(a_1,\dots ,a_n\right)$ 1. Initialize a queue $\mathrm{Q}$ of lists so that each element of the input is in a list all by itself. 2. $Q=\left(\left[a_1\right],\left[a_2\right],\dots ,\left[a_n\right]\right)$ 3. while $|Q|⩾2$ : 4. dequeue the first two lists from $Q$ and MERGE the two lists together. 5. enqueue the result into $Q$.