10.6 큰 파일 정렬

문제

한 줄에 문자열 하나가 쓰여있는 20GB 짜리 파일이 있다고 하자. 이 파일을 정렬하려면 어떻게 해야할지 설명하라. 

 

해결법

면접관이 20GB라는 제한을 준다는 것은 메모리에 모두 올릴 수 없다는 것을 의미한다.

바로 여기서 힌트를 얻는것이다. 가용 메모리의 크기가 x라고 가정했을때 파일을 x로 쪼개고 x 만큼씩 정렬하고 정렬이 끝나면 파일 시스템에 저장할 것이다. 모든 파일의 정렬이 끝나면 하나씩 병합한다. 모든 파일의 병합이 끝나 완벽히 정렬된 파일을 얻는다. 이런 알고리즘을 외부 정렬이라고 한다. 

 

외부링크에 대한 참고링크

https://dudri63.github.io/2019/02/03/algo32/