Skip to content
{}

Lesson 04new · v2 format

Two Indexes, One Loop: Merge, Compact & Partition

When one index isn't enough: two pointers that move at different times are behind merge sort, quick sort and half of all array problems.

30 min

01Why it matters & the intuition

Merge sort, quick sort, 'remove duplicates', 'move zeros' and 'pair with sum' all use two indexes that move independently inside one loop. Once you can say what each index means and when it moves, these algorithms stop being memorised code and become two sentences you can write from scratch.

Think of it like…

Two people merge two queues at a ticket counter: each watches the front of their own queue and lets the earlier ticket through. Only the queue that just moved advances. When one queue empties, the rest of the other walks straight through.

02The code blocks

Each block: the template in Python and C++, a line-by-line trace (press play and watch the highlighted line and the variables), the mistakes that cost the most debugging time, and a recall drill. Do the drill without scrolling up— that’s what makes it stick.

Block 1

Merge two sorted lists

Use it for: Merge sort, merging intervals/k lists, intersection/union of sorted arrays.

1 · The template

python
i = j = 0
out = []
while i < len(a) and j < len(b):
    if a[i] <= b[j]:
        out.append(a[i])
        i += 1
    else:
        out.append(b[j])
        j += 1
out.extend(a[i:])
out.extend(b[j:])

2 · Watch it run, line by line

trace · pythona = [1, 4, 7], b = [2, 3, 9]
1/25
▶i = j = 0
2out = []
3while i < len(a) and j < len(b):
4    if a[i] <= b[j]:
5        out.append(a[i])
6        i += 1
7    else:
8        out.append(b[j])
9        j += 1
10out.extend(a[i:])
11out.extend(b[j:])

Variables

i
0
j
0
a
0
1
i
1
4
2
7
b
0
2
j
1
3
2
9
out[ ]
line 1 ›One index per input list, both at the start.

3 · Classic mistakes

  • while i < len(a) or j < len(b):With `or`, the loop continues after one list runs out and reads a[i] past its end.
  • Forgetting the leftover copyOne list always runs out first; its partner's tail is silently dropped.

4 · Recall it without looking

recall · fill the blanks
while i < len(a)  j < len(b):
    ...
out.extend()
out.extend(b[j:])

Block 2

Read pointer + write pointer

Use it for: Remove elements in place, remove duplicates from sorted, move zeros, compact/filter without a new list.

1 · The template

python
w = 0
for r in range(len(a)):
    if a[r] != val:
        a[w] = a[r]
        w += 1
# a[:w] holds the kept values

2 · Watch it run, line by line

trace · pythona = [3, 2, 2, 3, 4], val = 3
1/18
▶w = 0
2for r in range(len(a)):
3    if a[r] != val:
4        a[w] = a[r]
5        w += 1
6# a[:w] holds the kept values

Variables

val
3
w
0
a
0
3
w
1
2
2
2
3
3
4
4
line 1 ›w = where the next kept value goes. We remove every 3.

3 · Classic mistakes

  • a.remove(x) inside for x in aMutating a list while iterating it skips elements. Use a write pointer or build a new list.
  • a[r] = a[w]Backwards: data flows from the read pointer (r) to the write pointer (w).

4 · Recall it without looking

recall · fill the blank
w = 0
for r in range(len(a)):
    if a[r] != val:
        a[] = a[r]
        w += 1

Block 3

Two ends moving inward

Use it for: Pair sum on sorted data, container with most water, palindromes, 3-sum's inner loop.

1 · The template

python
l, r = 0, len(a) - 1
while l < r:
    s = a[l] + a[r]
    if s == target:
        break
    elif s < target:
        l += 1
    else:
        r -= 1

2 · Watch it run, line by line

trace · pythona = [1, 3, 4, 6, 9], target = 13
1/13
▶l, r = 0, len(a) - 1
2while l < r:
3    s = a[l] + a[r]
4    if s == target:
5        break
6    elif s < target:
7        l += 1
8    else:
9        r -= 1

Variables

target
13
l
0
r
4
a
0
1
l
1
3
2
4
3
6
4
9
r
line 1 ›Sorted input, target 13. Smallest at l, largest at r.

3 · Classic mistakes

  • Using it on unsorted inputMoving l right only guarantees a bigger sum when the array is sorted.
  • while l <= r:Allows l == r, pairing an element with itself.

4 · Recall it without looking

recall · fill the blank
while l < r:
    s = a[l] + a[r]
    if s == target:
        break
    elif s < target:
        
    else:
        r -= 1

Block 4

Partition around a pivot

Use it for: Quick sort, quickselect (k-th smallest), Dutch flag, 'evens before odds'.

1 · The template

python
pivot = a[hi]
i = lo
for j in range(lo, hi):
    if a[j] < pivot:
        a[i], a[j] = a[j], a[i]
        i += 1
a[i], a[hi] = a[hi], a[i]

2 · Watch it run, line by line

trace · pythona = [7, 2, 9, 1, 5], lo = 0, hi = 4
1/15
▶pivot = a[hi]
2i = lo
3for j in range(lo, hi):
4    if a[j] < pivot:
5        a[i], a[j] = a[j], a[i]
6        i += 1
7a[i], a[hi] = a[hi], a[i]

Variables

lo
0
hi
4
pivot
5
a
0
7
1
2
2
9
3
1
4
5
line 1 ›Pivot = 5 (last element).

3 · Classic mistakes

  • for j in range(lo, hi + 1):Includes the pivot itself in the scan and can move it before the final placement.
  • Forgetting the final swapThe pivot stays at hi instead of landing between the two zones.

4 · Recall it without looking

recall · fill the blanks
pivot = a[hi]
i = lo
for j in range(lo, ):
    if a[j] < pivot:
        a[i], a[j] = a[j], a[i]
        
a[i], a[hi] = a[hi], a[i]

03Key ideas

Name each index by its job

i/j = next unread item in list a/b. r = reader, w = next write slot. l/r = the two ends. If you can't name the job, you can't write the condition.

Move only the index that consumed something

In merge, after taking a[i] only i moves. In write-pointer, r always moves but w moves only on a write.

Loop while both are valid, then clean up

Two-list loops use and in the condition and handle leftovers after the loop. Forgetting the cleanup is the most common merge bug.

Invariant = a sentence that stays true

Partition: 'everything in a[lo..i−1] is < pivot'. Write it as a comment; every line of the loop exists to keep it true.

04Cheat sheet

Every block from this lesson on one screen. Keep it open while you do the lab — then try the lab again without it.

python
# merge two sorted lists
i = j = 0; out = []
while i < len(a) and j < len(b):
    if a[i] <= b[j]: out.append(a[i]); i += 1
    else:            out.append(b[j]); j += 1
out += a[i:] + b[j:]

# read/write pointer: keep what passes a test
w = 0
for r in range(len(a)):
    if keep(a[r]):
        a[w] = a[r]; w += 1

# two ends (sorted input)
l, r = 0, len(a) - 1
while l < r:
    ...  # move l right to grow, r left to shrink

# partition around pivot = a[hi]
i = lo
for j in range(lo, hi):
    if a[j] < a[hi]:
        a[i], a[j] = a[j], a[i]; i += 1
a[i], a[hi] = a[hi], a[i]

05Complexity

BlockTimeExtra space
Merge two sorted lists (m + n)O(m + n)O(m + n) for the output
Read/write pointer compactionO(n)O(1)
Two ends inwardO(n)O(1)
Partition (Lomuto)O(n)O(1)

06Check your understanding

Question 1

Q1.Merging [1, 5] and [2, 3, 4]: when the while loop ends, what is left to copy?

Question 2

Q2.In the read/write pointer pattern, after processing the whole array, w equals…

Question 3

Q3.Two ends on a sorted array, sum too large. Which move is correct?

07Code lab

Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.

Move zeros to the end

Move every 0 to the end of the list in place while keeping the order of the non-zero values, then return the list. Use the read/write pointer, then fill the tail with zeros.

function: move_zerosPython starts when you get here
Trackers & FlagsBig-O