merge audit

제출 전에는 병합 누락을 배열로 검수한다

분할 정복 오답은 기저보다 병합에서 자주 나온다. 특히 비교 후 남은 꼬리 구간을 빠뜨리면 답의 계약이 깨진다.

정상 병합 누락 경계

정상 병합

left 1 4 9
right 2 6
out 1 2 4 6 9
통과 비교가 끝난 뒤 left의 남은 9까지 append한다.

실패 병합

out 1 2 4 6 ?
남음 9
실패 한쪽 포인터가 끝났다는 이유로 다른 쪽 잔여 구간을 버렸다.
증상 길이는 줄어들고 상위 호출의 “정렬된 전체 배열 반환” 계약이 깨진다.
검수 항목 배열로 확인할 증거 실패 신호
기저 길이 0 또는 1이 그대로 반환된다. 무한 재귀, 빈 배열 예외
끝점 닫힌 구간/반열린 구간 표기가 한 가지로 유지된다. 중앙 원소 중복 또는 누락
병합 비교 루프 뒤 남은 꼬리 구간을 모두 붙인다. 정렬은 된 듯 보이나 길이가 줄어듦