bottom-up (nonrecursivemerge-sort there is nonrecursive version of array-based merge-sortwhich runs in ( log ntime it is bit faster than recursive merge-sort in practiceas it avoids the extra overheads of recursive calls and temporary memory at each level the main idea is to perform merge-sort bottom-upperforming the merges level by level going up the merge-sort tree given an input array of elementswe begin by merging every successive pair of elements into sorted runs of length two we merge these runs into runs of length fourmerge these new runs into runs of length eightand so onuntil the array is sorted to keep the space usage reasonablewe deploy second array that stores the merged runs (swapping input and output arrays after each iterationwe give python implementation in code fragment similar bottom-up approach can be used for sorting linked lists (see exercise - def merge(srcresultstartinc) """merge src[start:start+incand src[start+inc:start+ incinto result "" end start+inc boundary for run boundary for run end min(start+ inclen(src) xyz startstart+incstart index into run run result while end and end if src[xsrc[ ] result[zsrc[ ] + copy from run and increment else result[zsrc[ ] + copy from run and increment + increment to reflect new result if end result[ :end src[ :end copy remainder of run to output elif end result[ :end src[ :end copy remainder of run to output def merge sort( ) """sort the elements of python list using the merge-sort algorithm "" len( logn math ceil(math log( , )make temporary storage for dest srcdest [nonen for in ( for in range(logn))pass creates all runs of length each pass merges two length runs for in range( ) merge(srcdestji srcdest destsrc reverse roles of lists if is not src [ :nsrc[ :nadditional copy to get results to code fragment an implementation of the nonrecursive merge-sort algorithm