listing improved implementation of the merge sort algorithm sorts virtual subsequence in ascending order using merge sort def recmergesorttheseqfirstlasttmparray )the elements that comprise the virtual subsequence are indicated by the range [first lasttmparray is temporary storage used in the merging phase of the merge sort algorithm check the base casethe virtual sequence contains single item if first =last returnelse compute the mid point mid (first last/ split the sequence and perform the recursive step recmergesorttheseqfirstmidtmparray recmergesorttheseqmid+ lasttmparray merge the two ordered subsequences mergevirtualseqtheseqfirstmid+ last+ tmparray variable or created and passed into the recursive function before the first call our implementation uses the latter approach the mergevirtualseq(functionprovided in listing on the next pageis modified version of mergesortedlists(from section the original function was used to create new list that contained the elements resulting from merging two sorted lists this version is designed to work with two virtual mutable subsequences that are stored adjacent to each other within the physical sequence structuretheseq since the two virtual subsequences are always adjacent within the physical sequencethey can be specified by three array index variablesleftthe index of the first element in the left subsequencerightthe index of the first element in the right subsequenceand endthe index of the first element following the end of the right subsequence second difference in this version is how the resulting merged sequence is returned instead of creating new list structurethe merged sequence is stored back into the physical structure within the elements occupied by the two virtual subsequences the tmparray argument provides temporary array needed for intermediate storage during the merging of the two subsequences the array must be large enough to hold all of the elements from both subsequences this temporary storage is needed since the resulting sorted sequence is not returned by the function but instead is copied back to the original sequence structure during the merging operationthe elements from the two subsequences are saved into the temporary array after being mergedthe elements are copied from the temporary array back to the original structure we could create new array each time the function is calledwhich would then be deleted when the function terminates but that requires additional overhead that is compounded by the many calls to the mergevirtualseq(function during the execution of the recursive recmergesort(function to reduce