병합 정렬은 배열을 반씩 나눠 한 원소가 될 때까지 내려갑니다. 되돌아오면서 두 정렬된 부분 배열의 앞 원소를 비교해 작은 값부터 새 배열에 넣습니다.
분할과 병합 단계가 반복돼 시간 복잡도는 O(n log n)입니다. 일반적인 배열 구현은 병합 결과를 담을 추가 공간이 필요합니다.
언제 쓰나
안정적인 정렬 순서가 중요하거나 입력 크기에 따른 실행 시간을 예측해야 할 때 유용합니다.
병합 정렬
Merge sort
목록을 작은 묶음으로 나눈 뒤 정렬된 묶음을 합칩니다.
···
<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)