두 정렬 구간을 합치며 안정성을 유지하기 쉽습니다
보조 배열 O(N)을 쓰는 대신 동점 원소의 기존 순서를 보존해야 할 때 선택합니다.
O(N log N) 정렬도 안정성, 공간, 최악 비용이 다르다
병합 정렬, 중앙 피벗 퀵 정렬, 제자리 힙 정렬은 같은 평균 비용처럼 보여도 운영 특성이 다릅니다.
피벗을 기준으로 작은 값과 큰 값을 나눕니다
피벗 선택이 나쁘면 O(N^2)까지 떨어질 수 있습니다.
힙 구조를 이용해 최댓값이나 최솟값을 차례로 꺼냅니다
제자리 정렬이 가능하지만 안정 정렬은 아닙니다.
분할/병합 경계 디버깅
i/j 포인터 이동 조건이 특히 자주 틀립니다.
안정성
동일 키의 기존 순서를 유지해야 하면 병합 정렬 계열이
유리합니다.
공간
추가 메모리 제한이 강하면 힙 정렬이나 제자리 퀵 정렬을
검토합니다.
피벗
중앙값, 랜덤, median-of-three 선택이 최악 입력을 줄일 수
있습니다.