in the partitioning algorithmtwo array indiceseach in its own while loopstart at opposite ends of the array and step toward each otherlooking for items that need to be swapped when an index finds an item that needs to be swappedits while loop exits when both while loops exitthe items are swapped when both while loops exit and the indices have met or passed each otherthe partition is complete partitioning operates in linear (ntimemaking plus or comparisons and fewer than / swaps the partitioning algorithm may require extra tests in its inner while loops to prevent the indices running off the ends of the array quicksort partitions an array and then calls itself twice recursively to sort the two resulting subarrays subarrays of one element are already sortedthis can be base case for quicksort the pivot value for partition in quicksort is the key value of specific itemcalled the pivot in simple version of quicksortthe pivot can always be the item at the right end of the subarray during the partition the pivot is placed out of the way on the rightand is not involved in the partitioning process later the pivot is swapped againinto the sace between the two partitions this is its final sorted position in the simple version of quicksortperformance is only ( for already sorted (or inversely sorteddata in more advanced version of quicksortthe pivot can be the median of the firstlastand center items in the subarray this is called median-of-three partitioning median-of-three partitioning effectively eliminates the problem of ( performance for already sorted data in median-of-three partitioningthe leftcenterand right items are sorted at the same time the median is determined this sort eliminates the need for the end-of-array tests in the inner while loops in the partitioning algorithm quicksort operates in ( *log ntime (except when the simpler version is applied to already sorted datasubarrays smaller than certain size (the cutoffcan be sorted by method other than quicksort