On analyzing recursive mergesort, one realizes that it can also be implemented **iteratively** (or bottom-up). Here...

Transcribed Image Text:

On analyzing recursive mergesort, one realizes that it can also be implemented **iteratively** (or bottom-up). Here is the idea: 1. Initially, each element in the array is moved into its own queue. 1. All the queues are put into a main queue (in order, from left to right). 1. Now, we repeatedly pull out two queues from the front of the main queue, merge the elements (using only queue operations and comparisons) into a new queue, and add the queue back to the rear of the main queue. 1. Repeat the previous step until the main queue has just one queue remaining inside it. 1. Move the contents of the last remaining queue back to an output array. Implement this algorithm by completing the provided stub code. You can **only** use builtin 'Queue' operations "get", "put' and 'empty with the queues: do not implement the queues as lists or any other data type. provide a clear argument for why the algorithm correctly sorts the input. Also provide an analysis of the runtime complexity (as a function of `n`, the number of elements of the inmput array). You can assume that the 'Queue' operations ("get", "put and empty') and comparisons etc. can be performed in constant time. On analyzing recursive mergesort, one realizes that it can also be implemented **iteratively** (or bottom-up). Here is the idea: 1. Initially, each element in the array is moved into its own queue. 1. All the queues are put into a main queue (in order, from left to right). 1. Now, we repeatedly pull out two queues from the front of the main queue, merge the elements (using only queue operations and comparisons) into a new queue, and add the queue back to the rear of the main queue. 1. Repeat the previous step until the main queue has just one queue remaining inside it. 1. Move the contents of the last remaining queue back to an output array. Implement this algorithm by completing the provided stub code. You can **only** use builtin 'Queue' operations "get", "put' and 'empty with the queues: do not implement the queues as lists or any other data type. provide a clear argument for why the algorithm correctly sorts the input. Also provide an analysis of the runtime complexity (as a function of `n`, the number of elements of the inmput array). You can assume that the 'Queue' operations ("get", "put and empty') and comparisons etc. can be performed in constant time.

Answer rating: 100% (QA)

Below is a Python implementation of the iterative bottomup merge sort algorithm using the queueQueue ... View the full answer