1병합 정렬로 줄 세우기

 

1 | 학생들에게 일일이 지시하는 것이 귀찮아진 선생님은 학생들이 알아서 줄을 설 수 있는 방법이 없을지 고민입니다. 열 명이나 되는 학생들에게 동시에 알아서 줄을 서라고 하면 너무 소란스러울 것 같아서, 다섯 명씩 두 조로 나누어 그 안에서 키 순서로 줄을 서라고 시켰습니다.

2 | 이제 선생님 앞에는 키 순서대로 정렬된 두 줄(중간 결과 줄)이 있습니다.

3 | 선생님은 각 줄의 맨 앞에 있는 두 학생 중에 키가 더 작은 민수를 뽑아 최종 결과 줄에 세웁니다. 그리고 다시 각 중간 결과 줄의 맨 앞에 있는 두 학생을 비교해 더 작은 학생을 최종 결과 줄의 민수 뒤에 세웁니다.

4| 이 과정을 반복하다가 중간 결과 줄 하나가 사라지면 나머지 중간 결과 줄에 있는 사람을 전부 최종 결과 줄에 세웁니다.

 

그림 10-1 병합 정렬