외부 정렬(External sort)

: 정렬해야하는 목적 데이터의 양이 큰 경우 사용한다.

“메인 메모리의 양이 100MB인데, 정렬해야 할 데이터가 10GB이면 어떻게 해야하는가?”

“한 줄에 한 문자열이 쓰여있는 텍스트 파일인데 이게 20GB이다. 어떻게 할 것인가?”

• 위와 같은 경우에 사용될 수 있는 것이 외부 정렬이다.
• 내부 정렬의 경우 일반적으로 성능 좋다고 알려진 퀵 or 합병 정렬을 사용하면 된다.

방법

1. 메인메모리에서 읽을 수 있는 단위(n MB)만큼 Disk로부터 읽고, 일반적인 방법(퀵 정렬)로 정렬한 후, 다시 디스크에 쓴다.
   • 이 작업이 끝나면, 디스크에 존재하는 m개의 청크(블록. chunk) 각각은 정렬되어있는 청크이다.
2. m개의 청크중 두개를 n / (m + 1) 만큼 디스크에서 읽어와, 병합을 진행하면서, 정렬 결과를 출력버퍼에 넣어 계속 디스크에 write한다.
3. 2번의 과정을 반복하다보면, m개의 청크는 회를 거듭하면서 m / 2, m / 4로 줄게 되고, 결국 하나의 정렬된 청크가 디스크에 남게 된다.

성능

• PASS: Disk에 데이터를 write, read하는 과정을 PASS라고 한다.
• 패스를 줄이는 요건인 메모리의 크기가 중요하다. 메모리 크기가 두배가 되면 청크 수와 청크 당 읽기 수가 절반으로 줄어든다.
• -> 결국 O(log(N/M)) (N: Input data, M: Main memory)

Reference)

코딩 인터뷰 완전분석

https://en.wikipedia.org/wiki/External_sorting