[정렬] 외부 병합 정렬

디스크에 정렬할 데이터가 1024MB가 있는데 RAM이 200MB뿐이라면 정렬을 어떻게 해야할까??

.

.

.

사실 이와 비슷한 질문을 여러번 받았었는데, 지금까지 정확한 답변은 찾지 못하고

단순히 나의 머릿속으로만 데이터를 분할 해서 정렬 하면 되지 않을까?

분할 정렬이니 분할 정복 방식 중 데이터를 쪼개어 정렬할 수 있는 머지소트를 이용하면 되지 않을까?

라고 생각하고만 있었다.

 

그러다 우연찮게 정확한 답변을 찾게 되었다.

바로 외부 병합 정렬.

 

외부 병합 정렬 ( external merge sort )

말 그대로 내부 메모리 뿐만 아니라 외부 디스크까지 활용해 정렬을 하는 방식이다.

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC#%EC%99%B8%EB%B6%80_%EB%B3%91%ED%95%A9_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

위키에도 나와있고 생각보다 오래부터 많이 이용한 방식이라고 한다.

 

기본적인 아이디어는

1. 메모리에 담을 수 있는 만큼 데이터를 읽고 퀵소트와 같은 일반적인 정렬 알고리즘으로 정렬한다.

2. 정렬된 데이터를 다시 디스크에 저장한다.

3. 1,2 번 방법으로 정렬된 파일 조각 여러개를 만든다.

4. n개로 쪼개진 데이터를 각각의 파일에서 순차적으로 조금씩만 읽어와 n-way merge sort를 수행한다.

5. 출력버퍼에 정렬된 데이터를 입력하고 출력버퍼가 차면 파일에 쓴다.

 

마치며

요즘도 메모리가 아무리 커졌다고는 하지만 메모리를 넘어서는 빅데이터를 활용하고 있기 때문에 충분히 실무에서 활용될 수 있는 개념이 아닐까싶다.