정렬할 데이터 들이 RAM용량을 훨씬 초과할 경우 효율적인 정렬법?

[DoWhile(windows12)]

1. 특정 파일에 int형 데이터 1000만개가 들어있음. 값의 중복은 없고 순서는 막 섞여 있음.

2. 시스템의 RAM용량이 무척 적어 한순간에 int형 데이터를 100만개 까지만 담고 있을 수 있음.

3. int데이터를 RAM으로 불러 들일 때 압축을 한다던가 하는것은 허용 안됨.

5. 정렬된 데이터를 다른 새 파일에 출력함으로써 결과 만들어 내면 됨.

이 상황에서 어떻게 하면 가장 효율적으로 정렬해낼수 있을까?

[DoWhile(windows12)]

내가 이런 상황에 처한건 아니고. 그냥 궁금해서.

[codesafer(codesafer)]

기본적인 external sort 100만개씩 부분정렬 저장후 merge

[codesafer(codesafer)]

external sort 로 검색해보면 예제들 많을듯

[우물개구리(whiteprince)]

생각하는 프로그래머 첫파트에 이 얘기 나옴

[codesafer(codesafer)]

근데 다 int면 radix 로 테이블 뜨면 되잖

[DoWhile(windows12)]

오 그런 용어가 있었구나. 그러니까 형 말은 파일 앞 부분부터 100만개 단위로 읽어 들인후 그 부분만 정렬하고 그 부분을 별도 파일로 출력하고, 결국 파일 10개가 새로 생기니까 이 파일 10개를 한번에 열어서 앞부분 부터 조금씩만 읽으면서 머지 해나가면 된다는 거지?

[codesafer(codesafer)]

응 파일이 더 작게 여러개 생기는데 꼭 이렇게 할 필욘 없어

[DoWhile(windows12)]

글쿠나 기수정렬 좀 공부해 봐야겠다.