/*internal method that merges two sorted halves of subarray is an array of comparable items tmparray is an array to place the merged result leftpos is the left-most index of the subarray rightpos is the index of the start of the second half rightend is the right-most index of the subarray *template void mergevector avector tmparrayint leftposint rightposint rightend int leftend rightpos int tmppos leftposint numelements rightend leftpos /main loop whileleftpos <leftend &rightpos <rightend ifaleftpos <arightpos tmparraytmppos+std::movealeftpos+)else tmparraytmppos+std::movearightpos+)whileleftpos <leftend /copy rest of first half tmparraytmppos+std::movealeftpos+)whilerightpos <rightend /copy rest of right half tmparraytmppos+std::movearightpos+)/copy tmparray back forint numelements++ --rightend arightend std::movetmparrayrightend )figure merge routine time to do two recursive mergesorts of size / plus the time to mergewhich is linear the following equations say this exactlyt( ( ( / this is standard recurrence relationwhich can be solved several ways we will show two methods the first idea is to divide the recurrence relation through by the reason for doing this will become apparent soon this yields