chap internal sorting static int partition( [aint lint re pivotdo /move bounds inward until they meet while ( [++lcompareto(pivot)< )while (( != &( [--rcompareto(pivot)> ))dsutil swap(alr)/swap out-of-place values while ( )/stop when they cross dsutil swap(alr)/reverse lastwasted swap return /return first position in right partition figure illustrates partition initiallyvariables and are immediately outside the actual bounds of the subarray being partitioned each pass through the outer do loop moves the counters and inwardsuntil eventually they meet note that at each iteration of the inner while loopsthe bounds are moved prior to checking against the pivot value this ensures that progress is made by each while loopeven when the two values swapped on the last iteration of the do loop were equal to the pivot also note the check that in the second while loop this ensures that does not run off the low end of the partition in the case where the pivot is the least value in that partition function partition returns the first index of the right partition so that the subarray bound for the recursive calls to qsort can be determined figure illustrates the complete quicksort algorithm to analyze quicksortwe first analyze the findpivot and partition functions operating on subarray of length clearlyfindpivot takes constant time function partition contains do loop with two nested while loops the total cost of the partition operation is constrained by how far and can move inwards in particularthese two bounds variables together can move total of steps for subarray of length howeverthis does not directly tell us how much work is done by the nested while loops the do loop as whole is guaranteed to move both and inward at least one position on each first pass each while loop moves its variable at least once (except in the special case where is at the left edge of the arraybut this can happen only oncethuswe see that the do loop can be executed at most timesthe total amount of work done moving and is sand each while loop can fail its test at most times the total work for the entire partition function is therefore th(sknowing the cost of findpivot and partitionwe can determine the cost of quicksort we begin with worst-case analysis the worst case will occur when the pivot does poor job of breaking the arraythat iswhen there are no elements in one partitionand elements in the other in this casethe divide and conquer strategy has done poor job of dividingso the conquer phase will work on subproblem only one less than the size of the original problem if this