1.
Run 탐지
•
입력 배열을 훑으면서 이미 오름차순(또는 내림차순)으로 정렬된 구간(run) 을 찾습니다.
•
내림차순 run은 뒤집어서 오름차순으로 맞추고, 길이가 너무 짧은 run은 이진 삽입 정렬로 확장합니다.
•
minrun(보통 32~64 사이)이라는 최소 run 길이를 목표로 하여, 나중 병합 비용을 줄입니다.
2.
Run 스택과 불변식(Invariants)
•
찾은 run들을 스택에 쌓고, 스택의 인접 run 크기 관계를 제어하는 불변식을 유지합니다.
•
이 불변식은 병합 순서를 조절하여 병합의 총 비용을 상한하고 **최악의 경우에도 O(n log n)**을 보장합니다.
3.
병합(Merge) + 갈로핑(Galloping) 모드
•
병합은 기본적으로 전형적인 안정 병합(merge) 입니다.
•
두 run 중 하나의 원소가 연속으로 많이 선택되는 상황이 감지되면 갈로핑(galloping) 으로 전환해 이진 탐색 기반으로 큰 덩어리를 한 번에 복사하여 속도를 높입니다. (데이터가 한쪽 run에 몰려 있으면 매우 효율적)
4.
적응성(Adaptive)
•
이미 정렬된 입력, 거의 정렬된 입력, 작은 블록들이 일부 섞인 입력에서 특히 효율적입니다.
•
그래서 “이미 어느 정도 정렬된 리스트를 다시 정렬”하는 실제 UI 시나리오에 강합니다.
