sorting /*mergesort algorithm (driver*template void mergesortvector vector tmparraya size)mergesortatmparray size )/*internal method that makes recursive calls is an array of comparable items tmparray is an array to place the merged result left is the left-most index of the subarray right is the right-most index of the subarray *template void mergesortvector avector tmparrayint leftint right ifleft right int center left right mergesortatmparrayleftcenter )mergesortatmparraycenter right )mergeatmparrayleftcenter right )figure mergesort routines temporary array active at any pointand that the temporary array can be created in the public mergesort driver furtherwe can use any part of the temporary arraywe will use the same portion as the input array this allows the improvement described at the end of this section figure implements the merge routine analysis of mergesort mergesort is classic example of the techniques used to analyze recursive routineswe have to write recurrence relation for the running time we will assume that is power of so that we always split into even halves for the time to mergesort is constantwhich we will denote by otherwisethe time to mergesort numbers is equal to the