heapq.merge에 정렬되지 않은 입력을 넣으면 전체 정렬되나

heapq.merge는 입력 iterable들이 이미 정렬되어 있다는 전제 아래 여러 정렬 스트림을 하나의 정렬된 iterator로 병합합니다. 각 입력이 정렬되지 않았다면 전체 출력이 정렬된다는 보장은 없습니다.

정렬되지 않은 한 스트림을 포함한 결과가 그 실행에서 어떻게 보이는지는 예제로 추적할 수 있지만, API 계약이 그 순서를 보장한다고 해석하면 안 됩니다. 임의 입력 전체를 정렬하려면 sorted()가 맞는 도구입니다.

merge는 정렬을 새로 하지 않고 정렬된 스트림을 합칩니다

Python 3.12의 heapq.merge는 여러 입력을 하나의 정렬된 결과로 병합하는 iterator를 돌려줍니다. 핵심은 입력 스트림마다 이미 같은 기준으로 정렬되어 있어야 한다는 전제입니다. 문서도 각 입력 스트림이 오름차순으로 정렬되어 있다고 가정한다고 명시합니다. 함수 이름에 merge가 들어간다고 해서 입력 전체를 다시 훑어 정렬하는 sorted와 같다고 생각하면 안 됩니다. 병합은 각 스트림의 현재 앞부분에서 다음 후보를 고르며 진행할 수 있습니다. 입력이 정렬되어 있으면 각 스트림의 다음 값은 이전 값보다 작지 않으므로, 앞에서 고른 최소값을 출력한 뒤 해당 스트림의 다음 값만 비교해도 전체 순서를 유지할 수 있습니다. 이 전제가 깨지면 이미 지나간 값보다 작은 값이 뒤늦게 나타날 수 있습니다. 그 값을 뒤로 되돌려 다시 배치하는 전 과정 정렬은 merge가 약속한 일이 아닙니다.

정렬된 입력에서는 앞의 최소값을 차례로 내보냅니다

첫 입력이 [1, 4, 7], 두 번째 입력이 [2, 3, 8]이라고 하겠습니다. 두 입력은 각각 오름차순입니다. 처음 비교할 후보는 1과 2이므로 1을 내보냅니다. 첫 입력에서 다음 값 4를 가져오면 후보는 4와 2가 되고, 2를 내보냅니다. 이후 3, 4, 7, 8 순서가 이어집니다. 각 스트림 내부의 순서가 유지되고 현재 후보 중 가장 작은 값을 선택하므로 최종 결과도 오름차순입니다. 이런 결과를 원소 전부를 한꺼번에 새 목록에 모아 정렬한 결과와 비교할 수는 있지만, 자료가 커질 때 merge는 입력 전체를 먼저 메모리에 올리는 방식이 아닙니다. 반환값도 목록이 아니라 필요할 때 값을 내주는 iterator입니다. 따라서 전체 입력을 저장하지 않고 정렬된 파일이나 기록을 이어 붙이는 작업에 맞습니다. 단, 스트림이 정렬되어 있다는 조건은 그대로 필요합니다.

from heapq import merge

left = [1, 4, 7]
right = [2, 3, 8]
print(list(merge(left, right)))

not_sorted = [1, 5, 3]
print(list(merge(not_sorted, [2, 4])))
print(sorted(not_sorted + [2, 4]))

두 번째 행의 출력은 현재 로컬 Python 3.12.10에서 해당 입력으로 실행했을 때 얻은 교육용 관찰입니다. 이것을 정렬되지 않은 입력에 대한 공식적인 결과 규칙으로 외우지는 마세요. 문서가 보장하는 것은 입력 스트림들이 정렬되었을 때의 병합입니다. 보장 밖의 동작에 특정 결과를 붙이는 것은 다른 Python 버전이나 다른 입력에서 틀린 추론으로 이어집니다.

입력마다 정렬 여부를 확인한 다음 도구를 고릅니다

1. 각 iterable을 독립된 스트림으로 적고, 각 스트림의 앞에서 뒤로 값이 비감소하는지 확인합니다.
2. 모든 스트림이 같은 정렬 기준을 만족하면 heapq.merge를 선택합니다.
3. 하나라도 정렬되지 않았다면 merge가 전체를 정렬한다고 가정하지 않습니다.
4. 전체 원소를 정렬해야 한다면 입력들을 모아 sorted()를 적용할지 판단합니다.
5. 문제에서 출력값을 물으면 정렬 입력의 전제와 실제 코드의 입력 순서를 먼저 표시합니다.

key를 사용해 문자열의 길이처럼 별도 기준으로 병합할 때도 입력 스트림들은 그 기준에 맞춰 이미 정렬되어 있어야 합니다. 문자열 목록 ['aa', 'b', 'ccc']는 사전식으로 정렬되어 있어도 길이는 2, 1, 3으로 비감소하지 않습니다. key=len으로 병합하려면 각 입력을 길이 기준으로 준비해야 합니다. 정수에는 len을 적용할 수 없으므로 숫자에 key=len을 쓰는 예와 혼동하지 마세요. reverse=True처럼 역방향 정렬을 사용할 때는 모든 입력이 같은 역방향 기준을 만족하는지도 확인하세요. 정렬 기준이 서로 다르면 어느 쪽이 먼저라는 보장을 적용할 수 없습니다.

함수 이름만 보고 자동 정렬이라고 착각하지 않습니다

흔한 실수는 merge를 sort의 동의어처럼 읽는 것입니다. 두 용도는 다릅니다. sorted(records)는 iterable의 값들을 모아 새 정렬 목록을 돌려주고, heapq.merge(a, b)는 이미 정렬된 여러 입력을 순서대로 병합합니다. 입력이 정렬되어 있으면 병합 과정에서 전체 입력을 먼저 저장하지 않는 이점이 있지만, 그 조건을 준비하는 책임은 호출자에게 있습니다. 또 하나의 실수는 한 스트림만 정렬되어 있으면 충분하다고 보는 것입니다. 두 입력 중 하나가 역순이면 어느 시점에 작은 값이 다시 나올지 현재 앞부분만으로 알 수 없습니다. 시험 풀이에서는 모든 입력을 따로 한 줄씩 확인하고, 한 군데라도 역순이 보이면 ‘정렬 보장 조건 불충족’이라고 먼저 표시하세요. 그 뒤 실제 출력 추적과 API가 약속하는 범위를 분리하면 됩니다.