chap internal sorting some choices for increments will make shellsort run more efficiently than others in particularthe choice of increments described above ( - turns out to be relatively inefficient better choice is the following series based on division by three the analysis of shellsort is difficultso we must accept without proof that the average-case performance of shellsort (for "divisions by threeincrementsis ( other choices for the increment series can reduce this upper bound somewhat thusshellsort is substantially better than insertion sortor any of the th( sorts presented in section in factshellsort is competitive with the asymptotically better sorts to be presented whenever is of medium size shellsort illustrates how we can sometimes exploit the special properties of an algorithm (in this case insertion sorteven if in general that algorithm is unacceptably slow mergesort natural approach to problem solving is divide and conquer in terms of sortingwe might consider breaking the list to be sorted into piecesprocess the piecesand then put them back together somehow simple way to do this would be to split the list in halfsort the halvesand then merge the sorted halves together this is the idea behind mergesort mergesort is one of the simplest sorting algorithms conceptuallyand has good performance both in the asymptotic sense and in empirical running time surprisinglyeven though it is based on simple conceptit is relatively difficult to implement in practice figure illustrates mergesort pseudocode sketch of mergesort is as followslist mergesort(list inlistif (inlist length(< return inlist;list half of the items from inlistlist other half of the items from inlistreturn merge(mergesort( )mergesort( ))before discussing how to implement mergesortwe will first examine the merge function merging two sorted sublists is quite simple function merge examines the first element of each sublist and picks the smaller value as the smallest element overall this smaller value is removed from its sublist and placed into the output list merging continues in this waycomparing the front elements of the sublists and continually appending the smaller to the output list until no more input elements remain