sec mergesort figure an illustration of mergesort the first row shows eight numbers that are to be sorted mergesort will recursively subdivide the list into sublists of one element eachthen recombine the sublists the second row shows the four sublists of size created by the first merging pass the third row shows the two sublists of size created by the next merging pass on the sublists of row the last row shows the final sorted list created by merging the two sublists of row implementing mergesort presents number of technical difficulties the first decision is how to represent the lists mergesort lends itself well to sorting singly linked list because merging does not require random access to the list elements thusmergesort is the method of choice when the input is in the form of linked list implementing merge for linked lists is straightforwardbecause we need only remove items from the front of the input lists and append items to the output list breaking the input list into two equal halves presents some difficulty ideally we would just break the lists into front and back halves howevereven if we know the length of the list in advanceit would still be necessary to traverse halfway down the linked list to reach the beginning of the second half simpler methodwhich does not rely on knowing the length of the list in advanceassigns elements of the input list alternating between the two sublists the first element is assigned to the first sublistthe second element to the second sublistthe third to first sublistthe fourth to the second sublistand so on this requires one complete pass through the input list to build the sublists when the input to mergesort is an arraysplitting input into two subarrays is easy if we know the array bounds merging is also easy if we merge the subarrays into second array note that this approach requires twice the amount of space as any of the sorting methods presented so farwhich is serious disadvantage for mergesort it is possible to merge the subarrays without using second arraybut this is extremely difficult to do efficiently and is not really practical merging the two subarrays into second arraywhile simple to implementpresents another difficulty the merge process ends with the sorted list in the auxiliary array consider how the recursive nature of mergesort breaks the original array into subarraysas shown in figure mergesort is recursively called until subarrays of size have been createdrequiring log levels of recursion these subarrays are merged into