Worst case: If the array is in descending order (and no duplicates), insertion sort makes ~ ½ N 2 compares and ~ ½ N 2 exchanges.
Average case: To sort a randomly-ordered array with distinct keys, insertion sort uses ~ ¼ N 2 compares and ~ ¼ N 2 exchanges on average.
Def: An array is partially sorted if the number of inversions is ≤ c N. For partially-sorted arrays, insertion sort runs in linear time. Pf. Number of exchanges equals the number of inversions.
