Visual walkthrough — Multiple inheritance — Python's C3 linearization algorithm

We use one running family the whole way:

class A: pass
class B(A): pass
class C(A): pass
class D(B, C): pass

Everything below builds toward one answer: $L[D]=[D,B,C,A,\text{object}]$.

---

Step 1 — Draw the family and name every symbol

WHAT. Before any algebra, we draw the inheritance graph and agree on notation.

WHY. The whole algorithm is a rule about arrows in this picture. If you can't see the arrows, the rule is just symbol-pushing. Every letter we use is earned here.

PICTURE.

The one law we must never break:

That law is the reason C3 exists. Keep the picture in mind — every later step is just enforcing it.

---

Step 2 — The base case: where every linearization bottoms out

WHAT. We define the smallest possible linearization.

WHY. C3 is recursive — $L[D]$ is built from $L[B]$ and $L[C]$, which are built from $L[A]$, which is built from $L[O]$. Recursion needs a floor to stand on. $O$ has no parents, so its list is trivially itself.

PICTURE.

---

Step 3 — Linearize the easy classes A, B, C first

WHAT. We compute $L[A]$, then $L[B]$, then $L[C]$.

WHY. The master formula for $D$ needs its parents' lists as ingredients. We can't merge lists we haven't built yet — so we work bottom-up, from the floor $O$ toward $D$.

PICTURE.

$A$ has a single parent, $O$. The master rule with one parent barely does anything:

$L[A]=\underset{\text{put self first}}{\underbrace{A}}+\text{merge}(\underset{[O]}{\underbrace{L[O]}},\underset{\text{parent list}}{\underbrace{[O]}})=[A,O]$

Here merge just spits $O$ out (it's the head of both little lists and sits in nobody's tail), so:

$L[A]=[A,O],L[B]=[B,A,O],L[C]=[C,A,O]$

---

Step 4 — Write the master formula for D

WHAT. We assemble the top-level merge for $D$ but do not solve it yet.

WHY. Seeing the exact input to merge — and why the extra list at the end is there — makes the next steps obvious instead of magical.

PICTURE.

---

Step 5 — The merge, iteration by iteration (the heart)

WHAT. We run the merge loop and emit one class per iteration until every list is empty.

WHY. This loop is C3. Each iteration answers one question: "Which class is safe to place next?" — safe meaning no child of it is still waiting.

PICTURE.

Walk it with the figure:

Iter	Remaining lists	Try	Good?	Reason
1	[B,A,O] [C,A,O] [B,C]	B	✅	$B$ is in no tail → emit B
2	[A,O] [C,A,O] [C]	A	❌	$A$ sits in tail of list 2 (C,A,O) → skip
2	″	C	✅	head of list 2, in no tail → emit C
3	[A,O] [A,O] []	A	✅	now in no tail → emit A
4	[O] [O] []	O	✅	last one → emit O

Emitting in order: $B,C,A,O$. Prepend the $D$ we set aside:

$L[D]=[D,B,C,A,O]$

---

Step 6 — Verify against the child-before-parent law

WHAT. We check the emitted list against Step 1's law, arrow by arrow.

WHY. An algorithm you can't audit is a spell. This step turns "trust me" into "look, it holds".

PICTURE.

Reading $[D,B,C,A,O]$ left to right and checking every arrow from Step 1:

• $D$ before $B$ ✅ and $D$ before $C$ ✅
• $B$ before $A$ ✅ and $C$ before $A$ ✅
• $A$ before $O$ ✅
• $A$ appears once ✅ (not once-per-path)

Every arrow points forward in the list. The law holds. This matches real Python exactly:

---

Step 7 — The degenerate case: when NO good head exists

WHAT. We run the algorithm on a hierarchy that has no valid order, and watch it get stuck.

WHY. Contract rule: cover the limiting/broken case. You must recognise the TypeError and know it is a real impossibility, not a Python bug.

The clash: A(X, Y) demands $X$ before $Y$; B(Y, X) demands $Y$ before $X$. Then C(A, B):

$L[C]=C+\text{merge}(\underset{L[A]}{\underbrace{[A,X,Y,O]}},\underset{L[B]}{\underbrace{[B,Y,X,O]}},\underset{\text{parents}}{\underbrace{[A,B]}})$

PICTURE.

• Emit A ✅ → [X,Y,O] [B,Y,X,O] [B]
• Emit B ✅ (head of list 2, in no tail) → [X,Y,O] [Y,X,O] []
• Try X: sits in tail of list 2 (Y,X,O) → skip.
• Try Y (head of list 2): sits in tail of list 1 (X,Y,O) → skip.
• No list has a good head. Deadlock.

$\Rightarrow \text{TypeError: Cannot create a consistent MRO}$

---

The one-picture summary

The whole derivation compressed: bottom-up ingredients on the left, the merge queue draining in the middle, the emitted MRO on the right, with the winning skip (iteration 2) circled.

Recall Feynman retelling — the whole walkthrough in plain words

We drew the family tree and made one promise: nobody's parent gets asked before them. We started at the very top, object, whose list is just itself. Then we built the little lists for the simple twins B and C — each is "me then my parent A then object". For D we lined up three queues: B's list, C's list, and the written parent order [B, C]. Then we played a game: look at the front of each queue and ask "is anyone standing behind this class in another queue?" If yes, they're that class's child and must go first, so we wait. B was free, so out it went. A tried to go but C was hiding behind it, so A waited and C went. Then A was free, then object. Reading the winners in order gives D, B, C, A, object — and grandma A stands in line once, at the back, exactly as promised. Finally we showed the broken family where X wants to be before Y and Y wants to be before X: nobody can ever go first, everyone's stuck, and Python honestly says "I can't order this" instead of guessing.

---

Connections

• Parent · C3 linearization
• Method Resolution Order
• The Diamond Problem
• Single inheritance
• super() and cooperative inheritance
• Topological sort
• Mixins
• Composition vs Inheritance