병합정렬(Merge Sort)

병합 정렬(Merge Sort)

병합 정렬은 분할 정복기법과 재귀 알고리즘을 이용한 정렬 알고리즘입니다. 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 게속 둘로 쪼갠 후에 다시 크기 순으로 재배열하면서 원래 크기의 배열로 합칩니다. 이해를 돕기위해 아래의 개념을 보시면 좋을 것 같습니다!

개념

먼저 다음과 같이 1부터 8까지 총 9개의 숫자가 들어가 있는 배열이 있다고 가정해보겠습니다.

[2, 4, 6, 5, 7, 1, 3, 8]

하나의 배열을 두개로 나눕니다.

[2, 4, 6, 5] [7, 1, 3, 8]

그리고 다시 두개의 배열을 네개로 나눕니다.

[2, 4] [6, 5] [7, 1] [3, 8]

마지막으로 다시 네 개의 배열을 여덟개로 나눕니다.

[2] [4] [6] [5] [7] [1] [3] [8]

이제 더 이상 나눌 수 없으니 두 개씩 합치기 시작합니다.

합칠 때, 작은 숫자가 앞에, 큰 숫자를 뒤에 위치시킵니다.

[2, 4] [5, 6] [1, 7] [3, 8]

이제 네개의 배열을 두개로 합쳐줍니다.

[2, 4, 5, 6] [1, 3, 7, 8]

두개의 배열도 마찬가지로 크기 순으로 선택해가면서 하나로 합치면 정렬된 배열을 얻을 수 있습니다.

[1, 2, 3, 4, 5, 6, 7, 8]

예제를 보았을때 8 -> 4 -> 2 -> 1 식으로 전반적인 반복의 수는 점점 절반으로 줄어들기 때문에 O(logN)시간이 필요하며, 각 패스에서 병합할 때 모든 값들을 비교해야 하므로 O(N)시간이 소모됩니다. 따라서 총 시간 복잡도는 O(NlogN)입니다.

코드