static void qsort( [aint iint /quicksort int pivotindex findpivot(aij)/pick pivot dsutil swap(apivotindexj)/stick pivot at end / will be the first position in the right subarray int partition(ai- ja[ ])dsutil swap(akj)/put pivot in place if (( - qsort(aik- )/sort left partition if (( - qsort(ak+ )/sort right partition function partition will move records to the appropriate partition and then return kthe first position in the right partition note that the pivot value is initially placed at the end of the array (position jthuspartition must not affect the value of array position after partitioningthe pivot value is placed in position kwhich is its correct position in the finalsorted array by doing sowe guarantee that at least one value (the pivotwill not be processed in the recursive calls to qsort even if bad pivot is selectedyielding completely empty partition to one side of the pivotthe larger partition will contain at most elements selecting pivot can be done in many ways the simplest is to use the first key howeverif the input is sorted or reverse sortedthis will produce poor partitioning with all values to one side of the pivot it is better to pick value at randomthereby reducing the chance of bad input order affecting the sort unfortunatelyusing random number generator is relatively expensiveand we can do nearly as well by selecting the middle position in the array here is simple findpivot functionstatic int findpivot( [aint iint jreturn ( + )/ we now turn to function partition if we knew in advance how many keys are less than the pivotpartition could simply copy elements with key values less than the pivot to the low end of the arrayand elements with larger keys to the high end because we do not know in advance how many keys are less than the pivotwe use clever algorithm that moves indices inwards from the ends of the subarrayswapping values as necessary until the two indices meet here is java implementation for the partition step