Ready to begin
No records have been processed. Start with Next step.
SECTION 04 / 28
Insert one new value into a sorted list
![Insert 5 into [1,3,4,7,9] just before 7, producing [1,3,4,5,7,9].](/images/computational-thinking/week-6/insert-middle.png)
REAL COURSE DATA · SORT, GROUP AND VERIFY
Insert one value into a sorted list
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.
Insertion assumes the existing list is already sorted by the same rule. Read it from the beginning, copying old values into a new list. When x belongs before the current z, append x first, then copy z and the remaining old values.
For ascending order, the lecture uses x < z. Passing an equal z leaves it before the new x. The algorithm inserts one occurrence; it does not remove an equal value or deduplicate the input. The output has one more element than the input.
Returning the new list does not automatically change a caller variable. Store it with L = SortedListInsert(L,x). A sortedness check alone is insufficient: also ensure every original occurrence and the new occurrence remain in the result.
Try it yourself
What must be true of the input list?
Show explained answer
It must already be sorted by the comparison key and direction used for insertion.
Try it yourself
If x equals an old value, should the old occurrence disappear?
Show explained answer
No. Insertion adds an occurrence. Equality does not imply replacement.
Try it yourself
Why copy the current z after inserting x before it?
Show explained answer
z is an original element that still belongs in the output. Inserting x does not consume or replace z.