then the split will be as even as possible unfortunatelythere is no quick guaranteed way of finding the optimal pivot if the keys are integersone could take the average value of all the keysbut that requires visiting all the entries to sample their keyadding considerable overhead to the algorithmand if the keys are more complicatedsuch as stringsyou cannot do this at all more importantlyit would not necessarily give pivot that is value in the array some sensible heuristic pivot choice strategies areuse random number generator to produce an index and then use [ktake key from 'the middleof the arraythat is [( - )/ take small sample ( or itemsand take the 'middlekey of those note that one should never simply choose the first or last key in the array as the pivotbecause if the array is almost sorted alreadythat will lead to the particularly bad choice mentioned aboveand this situation is actually quite common in practice since there are so many reasonable possibilitiesand they are all fairly straightforwardwe will not give specific implementation for any of these pivot choosing strategiesbut just assume that we have choosepivot( ,left,rightprocedure that returns the index of the pivot for particular sub-array (rather than the pivot value itselfthe partitioning in order to carry out the partitioning within the given arraysome thought is required as to how this may be best achieved this is more easily demonstrated by an example than put into words for changewe will consider an array of stringsnamely the programming languages[cfortranjavaadapascalbasichaskellocamlthe ordering we choose is the standard lexicographic oneand let the chosen pivot be "fortranwe will use markers to denote partition of the array to the left of the left markerthere will be items we know to have key smaller than or equal to the pivot to the right of the right markerthere will be items we know to have key bigger than or equal to the pivot in the middlethere will be the items we have not yet considered note that this algorithm proceeds to investigate the items in the array from two sides we begin by swapping the pivot value to the end of the array where it can easily be kept separate from the sub-array creation processso we have the array[|cocamljavaadapascalbasichaskell fortranstarting from the leftwe find "cis less than "fortran"so we move the left marker one step to the right to give [ ocamljavaadapascalbasichaskell fortrannow "ocamlis greater than "fortran"so we stop on the left and proceed from the right insteadwithout moving the left marker we then find "haskellis bigger than "fortran"so we move the right marker to the left by onegiving [ ocamljavaadapascalbasichaskellfortrannow "basicis smaller than "fortran"so we have two keys"ocamland "basic"which are 'on the wrong sidewe therefore swap themwhich allows us to move both the left and the right marker one step further towards the middle this brings us to [cbasic javaadapascal ocamlhaskellfortrannow we proceed from the left once againbut "javais bigger than "fortran"so we stop there and switch to the right then "pascalis bigger than "fortran"so we move the right marker again we then find "ada"which is smaller than the pivotso we stop we have now got [cbasic javaadapascalocamlhaskellfortranas beforewe want to swap "javaand "ada"which leaves the left and the right markers in the same place[cbasicadajava pascalocamlhaskellfortran]so we