Home▸Physics & Mechanics▸Comparison-Sorting Lower Bound: Decision Tree and Kraft Strip (2D)

🌳 Comparison-Sorting Lower Bound: Decision Tree and Kraft Strip (2D)

The real decision tree of insertion, binary-insertion or merge sort, built by running the sort on every ordering of n items, drawn flat. A Kraft strip shows the leaves tiling length 1, and a depth histogram shows where they sit against the information-theoretic bound log2 n!.

Physics & Mechanics2DModerate60 FPS📱 Mobile-adapted🟠 Blender⇄ 3D version
Comparison-Sorting Lower Bound: Decision Tree and Kraft Strip (2D) ↗ Open standalone
⚙ Under the hood

The real decision tree of insertion, binary-insertion or merge sort, built by running the sort on every ordering of n items, drawn flat. A Kraft strip shows the leaves tiling length 1, and a depth histogram shows where they sit against the information-theoretic bound log2 n!.

comparison sortlower bounddecision treeKraft inequalityinformation theoryn log nBlender renderCanvas

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install

What did you find?

Add reproduction steps (optional)