static void mergesort( [ae[tempint lint rint ijkmid ( + )/ /select the midpoint if ( =rreturn/list has one element if ((mid- >thresholdmergesort(atemplmid)else inssort(almid- + )if (( -midthresholdmergesort(atempmid+ )else inssort(amid+ -mid)/do the merge operation firstcopy halves to temp for ( =li<=midi++temp[ia[ ]for ( = <= -midj++temp[ - + [ +mid]/merge sublists back to array for ( = , = , =lk<=rk++if (temp[icompareto(temp[ ])< [ktemp[ ++]else [ktemp[ --]analysis of mergesort is straightforwarddespite the fact that it is recursive algorithm the merging part takes time th(iwhere is the total length of the two subarrays being merged the array to be sorted is repeatedly split in half until subarrays of size are reachedat which time they are merged to be of size these merged to subarrays of size and so on as shown in figure thusthe depth of the recursion is log for elements (assume for simplicity that is power of twothe first level of recursion can be thought of as working on one array of size nthe next level working on two arrays of size / the next on four arrays of size / and so on the bottom of the recursion has arrays of size thusn arrays of size are merged (requiring total steps) / arrays of size (again requiring total steps) / arrays of size and so on at each of the log levels of recursionth(nwork is donefor total cost of th( log nthis cost is unaffected by the relative order of the values being sortedthus this analysis holds for the bestaverageand worst cases quicksort while mergesort uses the most obvious form of divide and conquer (split the list in half then sort the halves)it is not the only way that we can break down the sorting problem and we saw that doing the merge step for mergesort when using an array implementation is not so easy so perhaps different divide and conquer strategy might turn out to be more efficientquicksort is aptly named becausewhen properly implementedit is the fastest known general-purpose in-memory sorting algorithm in the average case it does not require the extra array needed by mergesortso it is space efficient as well quicksort is widely usedand is typically the algorithm implemented in library