sorting proof the average number of inversions is initially ( - )/ ( each swap removes only one inversionso ( swaps are required this is an example of lower-bound proof it is valid not only for insertion sortwhich performs adjacent exchanges implicitlybut also for other simple algorithms such as bubble sort and selection sortwhich we will not describe here in factit is valid over an entire class of sorting algorithmsincluding those undiscoveredthat perform only adjacent exchanges because of thisthis proof cannot be confirmed empirically although this lower-bound proof is rather simplein general proving lower bounds is much more complicated than proving upper bounds and in some cases resembles magic this lower bound shows us that in order for sorting algorithm to run in subquadraticor ( )timeit must do comparisons andin particularexchanges between elements that are far apart sorting algorithm makes progress by eliminating inversionsand to run efficientlyit must eliminate more than just one inversion per exchange shellsort shellsortnamed after its inventordonald shellwas one of the first algorithms to break the quadratic time barrieralthough it was not until several years after its initial discovery that subquadratic time bound was proven as suggested in the previous sectionit works by comparing elements that are distantthe distance between comparisons decreases as the algorithm runs until the last phasein which adjacent elements are compared for this reasonshellsort is sometimes referred to as diminishing increment sort shellsort uses sequenceh ht called the increment sequence any increment sequence will do as long as but some choices are better than others (we will discuss that issue laterafter phaseusing some increment hk for every iwe have [ < [ hk (where this makes sense)all elements spaced hk apart are sorted the file is then said to be hk -sorted for examplefigure shows an array after several phases of shellsort an important property of shellsort (which we state without proofis that an hk -sorted file that is then hk- -sorted remains hk -sorted if this were not the casethe algorithm would likely be of little valuesince work done by early phases would be undone by later phases the general strategy to hk -sort is for each positioniin hk hk place the element in the correct spot among ii hk hk and so on although this does not original after -sort after -sort after -sort figure shellsort after each pass