sorting int left right forwhileai pivot ++whilepivot aj --ifi std::swapai ]aj )else breakfigure small change to quicksortwhich breaks the algorithm some side effectsthis program will not work if you try to use it without change with simple pivoting strategybecause and start in the wrong place and there is no longer sentinel for the swapping action at line is sometimes written explicitlyfor speed purposes for the algorithm to be fastit is necessary to force the compiler to compile this code inline many compilers will do this automatically if swap is declared using inlinebut for those that do notthe difference can be significant finallylines and show why quicksort is so fast the inner loop of the algorithm consists of an increment/decrement (by which is fast) testand jump there is no extra juggling as there is in mergesort this code is still surprisingly tricky it is tempting to replace lines to with the statements in figure this does not workbecause there would be an infinite loop if [ia[jpivot analysis of quicksort like mergesortquicksort is recursivethereforeits analysis requires solving recurrence formula we will do the analysis for quicksortassuming random pivot (no medianof-three partitioningand no cutoff for small arrays we will take ( ( as in mergesort the running time of quicksort is equal to the running time of the two recursive calls plus the linear time spent in the partition (the pivot selection takes only constant timethis gives the basic quicksort relation (nt(it( cn ( where | is the number of elements in we will look at three cases worst-case analysis the pivot is the smallest elementall the time then and if we ignore ( which is insignificantthe recurrence is (nt( cnn> (