[Algorithm] 병합 정렬, Merge sorting - 안정적이고 빠르다

데이터를 정렬하는데는 다양한 방법이 있는데 그 중 시간 복잡도가 O(n lon n) 인 알고리즘이 빠른 편이라고 알려져 있다. 동일한 시간 복잡도를 가진 알고리즘으로는 quick sorting, merge sorting, heap sorting 등이 있다. 그 중 heap sorting을 가장 많이 사용했던 것 같긴 한데 오늘은 안정적이면서 이해하기 쉽고 외우기도 쉬운 merge sorting을 복기해보았다.

병합 정렬은 전체 데이터를 반씩 반씩 균일하게 나누어서 가장 작은 단위까지 쪼갠 후에 다시 합쳐서 비교하는 방식으로 정렬한다. 예를 들면, {7, 1, 4, 3} 라는 데이터를 내림차순으로 정렬해보자.

- {(7, 1), (4, 3)} // 2개씩 나눔

- {(1, 7), (3, 4)} // 각 나눠진 부분을 비교하여 정렬

이제 각 묶음은 정렬이 되었으니 각 묶음의 아이템들을 순차적으로 비교하여 나열하면 내림차순으로 정렬할 수 있다.

- 1과 3을 비교 ==> { 1, 7, 3, 4 }

- 1이 더 작으므로 1을 tmp에 넣고 7로 비교 대상 이동 ==> { 1, 7, 3, 4 }, tmp = { 1, x, x, x }

- 7과 3을 비교, 3이 더 작으므로 tmp에 넣고 4로 비교대상 이동 ==> { 1, 7, 3, 4 }, tmp = { 1, 3, x, x }

- 7과 4를 비교, 4가 더 작으므로 tmp에 넣고 이동할 비교대상 없음 ==> { 1, 7, 3, 4 }, tmp = { 1, 3, 4, x }

- 비교 대상이 남아있는 왼쪽 항목들을 tmp에 넣고 원 배열에 업데이트 ==> { 1, 3, 4, 7 }, tmp = { 1, 3, 4, 7 }

더 큰 데이터에 대해서도 이와같이 반씩 나누어 작은 단위부터 정렬 후 키워나가면서 정렬하는 방식이 병합 정렬이다.

위의 예시에서처럼 정렬된 값을 저장할 추가 배열(tmp)이 필요하며 원래 배열에 업데이트 하는 과정이 있기 때문에 배열의 사이즈가 커지면 메모리 및 추가적인 시간 복잡도가 늘어날 수 있다.