더치 내셔널 플래그 정렬 계산기

값이 딱 세 종류(0, 1, 2)뿐인 배열을 low, mid, high 세 포인터로 한 번만 훑어 정렬하는 방법입니다. 네덜란드 국기의 세 색 띠(빨강·하양·파랑)에 빗대 다익스트라가 이름 붙였습니다.

비교 기반 정렬의 O(n log n) 하한은 "어떤 값이든 올 수 있을 때"의 이야기입니다. 값의 가짓수가 3개로 고정되어 있으면 이 제약이 적용되지 않아, 배열을 한 번만 훑으면서 확정된 자리로 바로 옮기는 O(n) 방법이 가능해집니다.

[0, low)는 이미 0으로 확정된 구간, [low, mid)는 1로 확정된 구간, [mid, high]는 아직 확인 안 된 구간, (high, 끝)은 2로 확정된 구간입니다. mid가 가리키는 값에 따라 low나 high와 자리를 바꾸며 구간을 넓혀갑니다.

퀵정렬에서 같은 값이 많을 때 "작음/같음/큼" 세 구간으로 나누는 3-way 파티션이 바로 이 아이디어입니다. 중복값이 많은 배열에서 일반 2-way 파티션보다 훨씬 빠릅니다.