alternative implementations of merge-sort sorting linked lists the merge-sort algorithm can easily be adapted to use any form of basic queue as its container type in code fragment we provide such an implementationbased on use of the linkedqueue class from section the ( log nbound for merge-sort from proposition applies to this implementation as wellsince each basic operation runs in ( time when implemented with linked list we show an example execution of this version of the merge algorithm in figure def merge( ) """merge two sorted queue instances and into empty queue "" while not is emptyand not is empty) if firsts first) enqueue( dequeue) else enqueue( dequeue)move remaining elements of to while not is empty) enqueue( dequeue)move remaining elements of to while not is empty) enqueue( dequeue) def merge sort( ) """sort the elements of queue using the merge-sort algorithm "" len( if return list is already sorted divide linkedqueueor any other queue implementation linkedqueue while len( / move the first // elements to enqueue( dequeue)move the rest to while not is empty) enqueue( dequeue) conquer (with recursionsort first half merge sort( sort second half merge sort( merge results merge( smerge sorted halves back into code fragment an implementation of merge-sort using basic queue