of the two sorted sublists are copiedin (ntimeto new list then the sorted list is copied back into the original sequenceagain in (ntime in the merge functionthe first while loop takes care of merging the two sublists until one or the other sublist is empty the second and third while loops take care of finishing up whichever sublist had the left-over elements only one sublist will have left-over elements so only one condition on the second and third while loops will ever be true notice that the third while loop in the code is commented out copying elements from to stop in the third while loop is not necessary since they would only be copied right back to the same place when the contents of lst are copied back to the seq sequence this optimization speeds up merge sort little bit one other optimization is to pre-allocate one more list in which to copy values and then alternate between merging in the original and the pre-allocated copy in this way the overhead of creating and appending to lists is avoided coding either of these two optimizations does not improve the computational complexity of the algorithmbut can improve its overall performance slightly one criticism of the merge sort algorithm is that the elements of the two sublists cannot be merged without copying to new list and then back again other sorting methodslike quicksorthave the same ( log ncomplexity as merge sort and do not require an extra list the mergesort function calls helper function to get everything started it calls mergesortrecursively function with the sequence and the start and stop values which indicate the entire list should be sorted the start and stop parameters are used when splitting the list the list is not physically split when calling mergesortrecursively insteadthe start and stop values are used to compute the mid point between them and then the two halves are recursively sorted since each sublist is smallerwe can rest assured that the recursive call does its job and sorts the two sublists then we are left to merge the two sorted sublists by calling the merge function the base case for the recursive function is when the sublist size is at that point we have sorted sublist in fig the entire left half of the list has been sorted in additionthree sublists in the right half have been sorted and the third and fourth sublist are in the process of being merged together the green dots represent the portions of the sequence that are sorted and the black dots indicate the unsorted portion of the original sequence the red lines at the bottom reflect the recursive calls that are currently on the run-time stack the length of the red line shows the portion of the sequence that is being sorted by its corresponding recursive call the blue line underscores the two sublists currently being merged together the argument that merge sort runs in ( log ntime needs just bit of explanation the repetitive splitting of the list results in (log nsplits in the end we have lists of size if we were to count every merge that occurs there would be / merges at the bottomfollowed by / merges at the next leveland so on leading to this sum the number of merges >log log = this analysis would seem to suggest that the complexity of the merge sort algorithm is ( since there are roughly merges each of which is (nitself howeverthe this copy belongs to 'acha