on the other handif the input is presortedthe running time is ( )because the test in the inner for loop always fails immediately indeedif the input is almost sorted (this term will be more rigorously defined in the next section)insertion sort will run quickly because of this wide variationit is worth analyzing the average-case behavior of this algorithm it turns out that the average case is ( for insertion sortas well as for variety of other sorting algorithmsas the next section shows lower bound for simple sorting algorithms an inversion in an array of numbers is any ordered pair (ijhaving the property that but [ia[jin the example of the last sectionthe input list had nine inversionsnamely ( )( )( )( )( )( )( )( )and ( notice that this is exactly the number of swaps that needed to be (implicitlyperformed by insertion sort this is always the casebecause swapping two adjacent elements that are out of place removes exactly one inversionand sorted array has no inversions since there is (nother work involved in the algorithmthe running time of insertion sort is ( )where is the number of inversions in the original array thusinsertion sort runs in linear time if the number of inversions is (nwe can compute precise bounds on the average running time of insertion sort by computing the average number of inversions in permutation as usualdefining average is difficult proposition we will assume that there are no duplicate elements (if we allow duplicatesit is not even clear what the average number of duplicates isusing this assumptionwe can assume that the input is some permutation of the first integers (since only relative ordering is importantand that all are equally likely under these assumptionswe have the following theoremtheorem the average number of inversions in an array of distinct elements is ( )/ proof for any listlof elementsconsider lr the list in reverse order the reverse list of the example is consider any pair of two elements in the list (xywith clearlyin exactly one of and lr this ordered pair represents an inversion the total number of these pairs in list and its reverse lr is ( )/ thusan average list has half this amountor ( )/ inversions this theorem implies that insertion sort is quadratic on average it also provides very strong lower bound about any algorithm that only exchanges adjacent elements theorem any algorithm that sorts by exchanging adjacent elements requires ( time on average