must make its way to the top of the array this would occur if the keys are initially arranged from highest to lowestin the reverse of sorted order in this casethe number of comparisons will be one the first time through the for looptwo the second timeand so on thusthe total number of comparisons will be th( = in contrastconsider the best-case cost this occurs when the keys begin in sorted order from lowest to highest in this caseevery pass through the inner for loop will fail immediatelyand no values will be moved the total number of comparisons will be which is the number of times the outer for loop executes thusthe cost for insertion sort in the best case is th(nwhile the best case is significantly faster than the worst casethe worst case is usually more reliable indication of the "typicalrunning time howeverthere are situations where we can expect the input to be in sorted or nearly sorted order one example is when an already sorted list is slightly disorderedrestoring sorted order using insertion sort might be good idea if we know that the disordering is slight examples of algorithms that take advantage of insertion sort' best-case running time are the shellsort algorithm of section and the quicksort algorithm of section what is the average-case cost of insertion sortwhen record is processedthe number of times through the inner for loop depends on how far "out of orderthe record is in particularthe inner for loop is executed once for each key greater than the key of record that appears in array positions through - for examplein the leftmost column of figure the value is preceded by five values greater than each such occurrence is called an inversion the number of inversions ( the number of values greater than given value that occur prior to it in the arraywill determine the number of comparisons and swaps that must take place we need to determine what the average number of inversions will be for the record in position we expect on average that half of the keys in the first array positions will have value greater than that of the key at position thusthe average case should be about half the cost of the worst casewhich is still th( sothe average case is no better than the worst case in asymptotic complexity counting comparisons or swaps yields similar results because each time through the inner for loop yields both comparison and swapexcept the last ( the comparison that fails the inner for loop' test)which has no swap thusthe number of swaps for the entire sort operation is less than the number of comparisons this is in the best caseand th( in the average and worst cases