Analysis of Insertion Sort The average number of comparisons for insertion sort applied to a list of n items in random order is +O(m) The average number of assignments of items for insertion sort applied to a list of n items in random order is also +O(m) 4 The best case for contiguous insertion sort occurs when the list is already in order when insertion sort does nothing except n-1 comparisons of keys
Analysis of Insertion Sort ◆The average number of comparisons for insertion sort applied to a list of n items in random order is ◆The average number of assignments of items for insertion sort applied to a list of n items in random order is also ◆The best case for contiguous insertion sort occurs when the list is already in order, when insertion sort does nothing except n - 1 comparisons of keys
The worst case for contiguous insertion sort occurs when the list is in reverse order THEOREM 8.1 Verifying that a list of n entries is in the correct order requires at least n-1 comparisons of keys Insertion sort verifies that a list is correctly sorted as quickly as any method can
◆The worst case for contiguous insertion sort occurs when the list is in reverse order. THEOREM 8.1 Verifying that a list of n entries is in the correct order requires at least n-1 comparisons of keys. ◆Insertion sort verifies that a list is correctly sorted as quickly as any method can