메모리보다 큰 데이터를 정렬할 때 무엇을 쓰는가?

외부 정렬을 사용한다. 데이터를 작은 조각으로 나누어 정렬한 뒤, 이를 다시 합치는 방식을 취한다.

가장 흔한 방식은 외부 병합 정렬이다. 메모리에 올릴 수 있는 만큼 데이터를 읽어 정렬하고 임시 파일로 저장한다. 이를 '런(Run)'이라고 부른다.

이후 여러 런을 동시에 읽으며 가장 작은 값을 선택해 결과 파일에 쓴다. 이때 최소 힙(Min Heap)을 사용해 병합 속도를 높인다.

디스크를 읽고 쓰는 횟수가 전체 시간을 좌우한다. 메모리 버퍼를 키우고 한 번에 병합할 런 수를 조절해 병합 단계 수를 줄인다.