advanced sorting equal keys here' another subtle change you might be tempted to make in the partitionit(code if you run the partitionit(method on items that are all equal to the pivot valueyou will find that every comparison leads to swap swapping items with equal keys seems like waste of time the operators that compare pivot with the array elements in the while loops cause the extra swapping howeversuppose you try to fix this by replacing them with operators this indeed prevents the swapping of equal elementsbut it also causes leftptr and rightptr to end up at the ends of the array when the algorithm has finished as we'll see in the section on quicksortit' good for the pointers to end up in the middle of the arrayand very bad for them to end up at the ends so if partitionit(is going to be used for quicksortthe operators are the right way to goeven if they cause some unnecessary swapping efficiency of the partition algorithm the partition algorithm runs in (ntime it' easy to see why this is so when running the partition workshop appletthe two pointers start at opposite ends of the array and move toward each other at more or less constant ratestopping and swapping as they go when they meetthe partition is complete if there were twice as many items to partitionthe pointers would move at the same ratebut they would have twice as many items to compare and swapso the process would take twice as long thusthe running time is proportional to more specificallyfor each partition there will be + or + comparisons every item will be encountered and used in comparison by one or the other of the pointersleading to comparisonsbut the pointers overshoot each other before they find out they've "crossedor gone beyond each otherso there are one or two extra comparisons before the partition is complete the number of comparisons is independent of how the data is arranged (except for the uncertainty between one or two extra comparisons at the end of the scanthe number of swapshoweverdoes depend on how the data is arranged if it' inversely orderedand the pivot value divides the items in halfthen every pair of values must be swappedwhich is / swaps (remember in the partition workshop applet that the pivot value is selected randomlyso that the number of swaps for inversely sorted bars won' always be exactly / for random datathere will be fewer than / swaps in partitioneven if the pivot value is such that half the bars are shorter and half are taller this is because some bars will already be in the right place (short bars on the lefttall bars on the rightif the pivot value is higher (or lowerthan most of the barsthere will be even fewer swaps because only those few bars that are higher (or lowerthan the pivot will need to be swapped on averagefor random dataabout half the maximum number of swaps take place