합병 정렬(merge sort)

모두를 위한 컴퓨터 과학(데이비드말란 교수님) 강의

 

1.1. 합병 정렬

합병 정렬(병합 정렬)은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가는 정렬을 하는 방식이다.

분할 정복(divide and conquer) 알고리즘의 하나로 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다

 

1.2. 합병 정렬 구현

1) 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

n개의 원소가 있을 때 배열을 계속해서 반으로 나누기 때문에 호출되는 함수의 개수는 log N개

2) 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 다시 분할한다.
3) 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
합쳐지는 과정에서 각 원소들의 크기를 비교하므로 -> N번의 비교 과정이 필요

 

 

나누어지는 단계가 log N번이라는 것은 배열을 반씩 나누어가기 때문에 이해하기가 쉽다. 그러나 정렬해서 합병하는 단계는 왜 N번일까?

분할이 다 되면 배열의 크기 만큼의 임시 배열(추가적인 메모리)을 만들게 된다.

분할되어 있는 원소 i와 j를 비교하여 작은 수를 k에 넣고, 처리한 배열은 1씩 더해 이동시킨다. 다시 i와 j를 비교하여 더 작은 6을 k에 삽입하고 i와 k에 1씩 더해주는 과정을 진행한다.

 

1.3. 합병 정렬의 효율성

 

최악의 시나리오

숫자들을 반으로 나누는 데는 log N의 시간이 들고, 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 N의 시간

• O(N*logN)

 

최선의 시나리오

숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문에 최악의 시나리오와 같다.

• Ω(N*logN)