Split a list into small runs, then merge sorted runs.
<div class="v"><header><b>MERGE SORT</b><span id="state"></span></header><main><div class="runs" id="runs"></div><div class="result" id="result"></div></main><footer>split → merge</footer></div>.v{width:min(92vw,660px);height:min(86vh,310px);box-sizing:border-box;padding:clamp(9px,2.5vmin,18px);border:1px solid var(--line);border-radius:14px;background:var(--surface);display:flex;flex-direction:column;gap:7px;color:var(--fg);font:500 clamp(15px,4.5vmin,19px)/1.25 var(--font-sans, sans-serif)}.v header,.v footer{display:flex;justify-content:space-between;align-items:center;gap:8px;white-space:nowrap}.v header b{color:var(--accent);font-size:.9em}.v header span,.v footer{color:var(--muted);font-size:.82em}.v main{flex:1;min-height:0;position:relative;overflow:hidden}.v .mono{font-family:ui-monospace,SFMono-Regular,Consolas,monospace}.v .active{background:var(--accent)!important;color:var(--bg)!important;border-color:var(--accent)!important}.v .muted{opacity:.45} .v{width:min(92vw,900px);height:min(86vh,330px)}.runs{height:60%;display:flex;justify-content:center;align-items:center;gap:clamp(4px,2vw,18px)}.run{box-sizing:border-box;flex:1;max-width:260px;height:clamp(42px,10vmin,82px);display:flex;align-items:center;justify-content:center;gap:4px;padding:4px;border:1px dashed var(--line);border-radius:8px}.run b,.result b{box-sizing:border-box;width:clamp(26px,4vw,52px);height:clamp(26px,4vw,52px);display:grid;place-items:center;font:600 1em ui-monospace,monospace;border-radius:4px;background:color-mix(in srgb,var(--accent) 13%,var(--surface))}.result{height:38%;display:flex;align-items:center;justify-content:center;gap:4px}.result span{color:var(--accent);margin-right:5px}const levels=[[[4],[1],[3],[2]],[[1,4],[2,3]],[[1,2,3,4]]];let n=0;function draw(){let runs=levels[n];document.getElementById("runs").innerHTML=runs.map(r=>"<div class=run>"+r.map(x=>"<b>"+x+"</b>").join("")+"</div>").join("");document.getElementById("result").innerHTML=n===0?"<span>↓ split</span>":"<span>↓ merge</span><b>1</b><b>2</b><b>3</b><b>4</b>";document.getElementById("state").textContent=["split","merge pairs","merged"][n];n=(n+1)%3}draw();setInterval(draw,1100)Merge sort divides an array until each run has one item. On the way back, it compares the heads of two sorted runs and writes the smaller item to the merged result.
Repeated splitting and merging gives O(n log n) time. A typical array implementation needs extra space for the merged output.
Use it when stable ordering or predictable time across input sizes matters.