quicksort the general idea here is to repeatedly split (or partitionthe given array in such way that all the items in the first sub-array are smaller than all the items in the second sub-arrayand then concatenate all the sub-arrays to give the sorted full array how to partition the important question is how to perform this kind of splitting most efficiently if the array is very simplefor example [ , , , , , ]then good split would be to put all the items smaller than into one partgiving [ , , ]and all the items bigger than or equal to into the otherthat is [ , , indeedmoving all items with smaller key than some given value into one sub-arrayand all entries with bigger or equal key into the other sub-array is the standard quicksort strategy the value that defines the split is called the pivot howeverit is not obvious what is the best way to choose the pivot value one situation that we absolutely have to avoid is splitting the array into an empty subarray and the whole array again if we do thisthe algorithm will not just perform badlyit will not even terminate howeverif the pivot is chosen to be an item in the arrayand the pivot is kept in between and separate from both sub-arraysthen the sub-arrays being sorted at each recursion will always be at least one item shorter than the previous arrayand the algorithm is guaranteed to terminate thusit proves convenient to split the array at each stage into the sub-array of values smaller than or equal to some chosen pivot itemfollowed by that chosen pivot itemfollowed by the sub-array of values greater than or equal to the chosen pivot item moreoverto save spacewe do not actually split the array into smaller arrays insteadwe simply rearrange the whole array to reflect the splitting we say that we partition the arrayand the quicksort algorithm is then applied to the sub-arrays of this partitioned array in order for the algorithm to be called recursivelyto sort ever smaller parts of the original arraywe need to tell it which part of the array is currently under consideration thereforequicksort is called giving the lowest index (leftand highest index (rightof the sub-array it must work on thus the algorithm takes the formquicksort(array aint leftint rightif left right pivotindex partition( ,left,rightquicksort( ,left,pivotindex- quicksort( ,pivotindex+ ,rightfor which the initial call would be quicksort( , , - and the array at the end is sorted the crucial part of this is clearly the partition(aleftrightprocedure that rearranges the array so that it can be split around an appropriate pivot [pivotindexif we were to split off only one item at timequicksort would have recursive callswhere is the number of items in the array ifon the other handwe halve the array at each stageit would only need log recursive calls this can be made clear by drawing binary tree whose nodes are labelled by the sub-arrays that have been split off at each stageand measuring its height ideally thenwe would like to get two sub-arrays of roughly equal size (namely half of the given arraysince that is the most efficient way of doing this of coursethat depends on choosing good pivot