while [jdo : - endif < then : [ ] [ : [ ] [ :wi : + : - end until end partition as an exampleif the middle key is selected as comparand xthen the array of keys requires the two exchanges and to yield the partitioned array and the final index values and keys ai- are less or equal to key and keys aj+ an- are greater or equal to key consequentlythere are three partsnamely ak < ak < aki < < ak akj < - <ak the goal is to increase and decrease jso that the middle part vanishes this algorithm is very straightforward and efficient because the essential comparands ij and can be kept in fast registers throughout the scan howeverit can also be cumbersomeas witnessed by the case with identical keyswhich result in / exchanges these unnecessary exchanges might easily be eliminated by changing the scanning statements to while [ < do : + endwhile < [jdo : - end in this casehoweverthe choice element xwhich is present as member of the arrayno longer acts as sentinel for the two scans the array with all identical keys would cause the scans to go beyond the bounds of the array unless more complicated termination conditions were used the simplicity of the conditions is well worth the extra exchanges that occur relatively rarely in the average random case slight savinghowevermay be achieved by changing the clause controlling the exchange step to instead of < but this change must not be extended over the two statements : + : - which therefore require separate conditional clause confidence in the correctness of the partition algorithm can be gained by verifying that the ordering relations are invariants of the repeat statement initiallywith and - they are trivially trueand upon exit with jthey imply the desired result we now recall that our goal is not only to find partitions of the original array of itemsbut also to sort it howeverit is only small step from partitioning to sortingafter partitioning the arrayapply the same process to both partitionsthen to the partitions of the partitionsand so onuntil every partition consists of single item only this recipe is described as follows (note that sort should actually be declared local to quicksortprocedure sort (lrinteger)var ijintegerwxitembegin :lj :rx : [( +rdiv ]repeat (adens _sorts *