for defining the pivotsince the particular problem in question might well allow for more refined approach generallythe pivot will be better if more items are sampled before it is being chosen for exampleone could check several randomly chosen items and take the 'middleone of thosethe so called median note that in order to find the median of all the itemswithout sorting them firstwe would end up having to make comparisonsso we cannot do that without making quicksort unattractively slow quicksort is rarely the most suitable algorithm if the problem size is small the reason for this is all the overheads from the recursion ( storing all the return addresses and formal parametershence once the sub-problem become 'small( size of is often suggested in the literature)quicksort should stop calling itself and instead sort the remaining sub-arrays using simpler algorithm such as selection sort mergesort the other divide and conquer sorting strategy based on repeatedly splitting the array of items into two sub-arraysmentioned in section is called mergesort this simply splits the array at each stage into its first and last halfwithout any reordering of the items in it howeverthat will obviously not result in set of sorted sub-arrays that we can just append to each other at the end so mergesort needs another procedure merge that merges two sorted sub-arrays into another sorted array as with binary search in section integer variables left and right can be used to refer to the lower and upper index of the relevant arrayand mid refers to the end of its left sub-array thus suitable mergesort algorithm ismergesort(array aint leftint rightif left right mid (left right mergesort(aleftmidmergesort(amid+ rightmerge(aleftmidrightnote that it would be relatively simple to modify this mergesort algorithm to operate on linked lists (of known lengthrather than arrays to 'splitsuch list into twoall one has to do is set the pointer of the bn/ cth list entry to nulland use the previously-pointed-to next entry as the head of the new second list of coursecare needs to be taken to keep the list size information intactand effort is required to find the crucial pointer for each split the merge algorithm the principle of merging two sorted collections (whether they be listsarraysor something elseis quite simplesince they are sortedit is clear that the smallest item overall must be either the smallest item in the first collection or the smallest item in the second collection let us assume it is the smallest key in the first collection now the second smallest item overall must be either the second-smallest item in the first collectionor the smallest item in the second collectionand so on in other wordswe just work through both collections and at each stagethe 'nextitem is the current item in either the first or the second collection