An array of 10 elements is sorted in ascending order with insertion sort. Each element from the second one on is taken out and compared with the elements to its left, starting with its left neighbor, until an element less than or equal to it is found or the front is reached. How many comparisons are made when the array is already in ascending order, and when it is in descending order?

Answer: C. 9 and 45

If the array is already ascending, each element needs only one comparison with its left neighbor, so the 9 elements take 9 comparisons in total. If it is descending, the element taken out i-th is compared with all i elements to its left, giving 1 + 2 + … + 9 = 45. Insertion sort thus varies greatly with the input, O(n) in the best case and O(n²) in the worst, and it is very fast on nearly sorted data. Shell sort exploits this by first running insertion sort on elements a gap apart, and Timsort also uses insertion sort for short runs.

• A. Always making 45 comparisons is true of selection sort. For insertion sort the count depends on the input order.
• B. The element count 10 and 10² = 100 are not the comparison counts.
• C. Correct. Ascending order takes one comparison per element (9), and descending order takes 1 + 2 + … + 9 = 45.