Neural Sync Active

Computational Thinking · Week 5 — Lists & insertion sort

Registry Synced

Computational Thinking · Week 5 — Lists & insertion sort

1127 words

6 min read

2026-08-16

Reading compass

Now · Week map

Week 5 — lists & insertion sort

Quiz 2 scope: Weeks 1–8 per IITM May 2026 foundation courses. Source baseline: IITM BS admissions important-dates calendar · May 2026 cycle. Times on assessments are operational conventions — verify hall ticket.

Part of the Quiz 2 prep system · Weeks 1–8 index · Pattern atlas · Formula chains.

Week map

List ops → traverse → insertion sort shifts → sorted invariant

Classify → Represent → Execute → Trap-check

Recognize: Ask: What is sorted after outer index i in insertion sort?
Procedure: Build new list or update in place per spec. Keep index valid: 0 to len-1.
Variations / traps: Watch for: Shift direction wrong in insertion sort.

Formula chain (compressed)

list insert/delete → traversal index → insertion sort trace.

List index — L[i] read/write — 0-based positions
Insert — shift right, place key — insertion sort inner loop
Sorted prefix — L[0..i-1] sorted — insertion sort invariant
Compare-shift — while L[j-1] > key: shift — trace swaps
Stable sort — equal keys keep order — insertion sort property

Open interactive formula desk · Week 5 tab.

Deep study

Computational Thinking · Week 5 — Lists and insertion sort

Deep study for Quiz 2 week 5. Lists store ordered sequences; insertion sort builds a sorted prefix by shifting larger neighbors right.

Week map

List operations → 0-based indexing → traversal → insertion sort outer loop → inner shift → sorted invariant.

List notation (algorithmic view)

List → ordered sequence of items at positions $0, 1, \ldots, n-1$ .
len(L) → length $n$ .
L[i] → item at index $i$ → valid when $0 \leq i < n$ .
Append → add at end; insert → open slot at index, shift right.

Mini-example:

L = [5, 2, 8, 1]

L[0] = 5

L[-1] = 1

(last),

\text{len}(L) = 4

Traversal

Visit each position once:


text
for i from 0 to len(L)-1:
    process L[i]

Or while-index style with counter increment.

Insertion sort notation

Outer index $i$ → next element to insert into sorted prefix $L[0..i-1]$ .
Key → value at $L[i]$ to place correctly.
Inner index $j$ → walk backward while $L[j] > \text{key}$ , shift $L[j]$ right to $L[j+1]$ .
Invariant: after each outer step, $L[0..i]$ is sorted.

Mini-trace on

[3, 1, 4, 2]

$i$	key	after shifts	sorted prefix
1	1	[1, 3, 4, 2]	first 2
2	4	no shift	first 3
3	2	[1, 2, 3, 4]	all 4

Pattern families

Easy — Traverse and transform

Visit each index; compute sum, count, or build new list. Keep indices in range

0

\text{len}-1

Medium — One insertion sort pass

Given

i

and array state, trace inner shifts. Place key at final hole

j+1

Hard — Full sort trace

Table columns:

i

, key, array after each outer iteration. Count shifts. Already-sorted input: minimal inner work but outer still runs

n-1

times.

Worked mini-examples

Example 1 — Index access.

L = [10, 20, 30]

L[1] = 20

. Insert 15 at index 1 →

[10, 15, 20, 30]

Example 2 — One shift step.

Array

[2, 5, 5, 7]

, key

= 4

at position 2. Compare

L[1]=5 > 4

: shift →

[2, 5, 5, 7]

then

[2, 5, 5, 7]

... walk

j

from 1:

L[1]=5>4

shift to index 2 →

[2, 5, 5, 7]

;

L[0]=2 \not> 4

; place key at

j+1 = 1

→

[2, 4, 5, 7]

Example 3 — Sorted input.

[1, 2, 3]

: each key already in place — zero shifts, still

n-1

outer passes.

Example 4 — Reverse input.

[3, 2, 1]

: maximum shifts — roughly

1 + 2 = 3

shifts for

n=3

Example 5 — Locate after shifts.

Inner loop stops when

L[j] \leq \text{key}

j < 0

. Write key at

L[j+1]

Traps

Shift direction wrong — move larger elements right, not left.
Off-by-one: outer $i$ typically starts at 1 (first element trivially sorted).
Confusing insert index after multiple shifts.
Using $i$ past $\text{len}-1$ .
Assuming $O(n)$ because small $n$ in trace — algorithm is $O(n^2)$ comparisons in worst case.

Diagnostic (try yourself)

List $[7, 3, 9, 1]$ . What is index of element 9? What is $\text{len}$ ?
One outer step of insertion sort at $i=1$ on $[4, 2, 5]$ . Show array after placing key.
How many outer iterations for list of length 5?
After sorting $[5, 1, 4]$ , what is the invariant about $L[0..i]$ after each $i$ ?
Why does insertion sort do little work on already-sorted input?

ChatGPT prep archive

Chatty reference archive

Archived import for extra depth — complements the notes above, not official IITM material.

Core concepts

List ops: append, insert, length, index access; 0-based indexing.
Traversal: visit each position once with for or while index.
Insertion sort: for each position, shift larger elements right, insert into sorted prefix.
Invariant: items left of index are sorted after each outer step.

Notation & vocabulary

Step	Action
outer i	next element to place
inner j	shift while larger
insert	write key at hole

Pattern families

Easy — Traverse and transform

Build new list or update in place per spec. Keep index valid: 0 to len-1.

Medium — Insertion sort pass

Take element at i, walk j backward while arr[j] > key, shift arr[j+1]=arr[j], place key at j+1.

Hard — Full sort trace

Table columns: i, key, array after shifts. Sorted prefix grows one element per i. Already-sorted input still runs but minimal shifts.

Drill these on the pattern atlas — filter to week 5.

Traps

Shift direction wrong in insertion sort.
Using i past len-1.
Confusing insert index after shifts.
O(n²) trace confusion on small n—still trace mechanically.

Retrieval prompts

What is sorted after outer index i in insertion sort?
How does shift step work?
Difference traverse vs sort?

Practice loop

Read Deep study (if present) or core concepts once.
Recite the formula chain without looking.
Open one easy pattern on the interactive atlas for week 5.
Attempt without solutions; mark studied after an honest try.
Say one trap aloud before closing the tab.