Ready to begin
No records have been processed. Start with Next step.
SECTION 07 / 28
Build insertion sort and explain why it works
![For input [14,4,22,11], each completed prefix is sorted: [14], [4,14], [4,14,22], [4,11,14,22].](/images/computational-thinking/week-6/sort-invariant.png)
REAL COURSE DATA · SORT, GROUP AND VERIFY
Build a sorted view of score pairs
Follow the selected procedure. Change a field, tie rule or weekday and explain why the result changes.
Ready
What we remember
- Processed
- 0
Predict the next change. Keep track of which list level, field and position convention the procedure uses.
Procedure InsertionSort(L):
sortedList = []
foreach x in L:
sortedList = SortedListInsert(sortedList, x)
return sortedListAn invariant is a property maintained after each completed iteration. Here sortedList is sorted AND contains exactly the input occurrences processed so far. Initially [] satisfies both properties. A correct insertion adds one new occurrence while preserving sortedness.
When foreach ends, every input occurrence has been inserted, so the sorted output contains the complete input. This argument has an initial case, a preservation step and a final conclusion. It is stronger than saying the last displayed list “looks ordered”.
To reverse the sort direction, change x < z to x > z inside insertion. Reverse the key comparison, not the source record identities or the order of fields inside each pair.
Try it yourself
Is “the result is sorted” a complete correctness claim?
Show explained answer
No. An empty result is sorted but may have lost every input. You must also preserve all occurrences.
Try it yourself
Why is an empty initial result useful?
Show explained answer
It is already sorted, so it satisfies insertion’s precondition before the first call.
Try it yourself
Which change produces descending order?
Show explained answer
Insert before z when x > z instead of x < z.