⑥ 이 과정을 반복하면 다음과 같이 한 그룹의 자료가 다 빠져나가 비어 있게 됩니다.

g1: [8 9 10]

g2: []

result: [1 2 3 4 5 6 7]

 

⑦ g2에는 자료가 없으므로 비교할 필요 없이 g1에 남아 있는 값을 전부 result로 옮기면 정렬이 끝납니다.

g1: []

g2: []

result: [1 2 3 4 5 6 7 8 9 10]

 

이 방법을 병합 정렬이라 부르는 이유는 이미 정렬된 두 그룹을 맨 앞에서부터 비교하면서 하나로 합치는 ‘병합(merge)’ 과정이 정렬 알고리즘의 핵심이기 때문입니다(③~⑦번 과정).