Insertion sort builds a sorted section at the start of a list by inserting each new element into its correct position, shifting larger elements along to make room.
The nearly-sorted list [2, 5, 9, 14, 8, 20] is sorted using insertion sort.
State how many shifts are needed to insert 8 into its correct position within the already-sorted section 2, 5, 9, 14, and explain why insertion sort performs much better on a nearly-sorted list like this than on a list in reverse order, referring to its best-case and worst-case time complexities.
Answer
Two shifts: 14, then 9; insert 8 after 5, producing [2,5,8,9,14,20]. Nearly sorted data needs few shifts. An already sorted list takes O(n) comparisons overall; reverse order requires 1+2+...+(n-1) shifts and O(n^2) time.
Mark scheme
| A1 | for 2 shifts |
| A1 | for a count consistent with moving 14 and 9 past 8 |
| A1 | for insertion after 5. The latter two may be inferred from the correct count for the printed section. |
| B1 | for explaining that nearly sorted data needs few shifts |
| B1 | for best-case O(n) on already sorted input |
| B1 | for worst-case O(n^2) on reverse order because the shifts sum to 1+2+...+(n-1). Accept equivalent valid complexity explanations; an intermediate comparison trace is not required. |