합병 정렬(Merge Sort Algorithm)

합병 정렬은 분할 정복(Divide and Conquer) 방식으로 설계된 알고리즘이다.
분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해나가는 방식으로,
분할은 배열의 크기가 1보다 작거나 같을때까지 반복한다.

 

입력으로 하나의 배열을 받고, 연산 중에 두개의 배열로 계쏙 쪼개 나간 뒤, 합치면서 정렬해 최우에는 하나의 정렬을 출력한다.

 

합병은 두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해나간다.

오름차순의 경우 배열A, 배열B를 비교하여 배열A에 있는 값이 더 작다면 새 배열에 저장해주고, A인덱스를 증가시킨 후 A, B의 반복을 진행한다.

이는 A나 B중 하나가 모든 배열값들을 새 배열에 저장할 때 까지 반복하며, 전부 다 저장하지 못한 배열의 값들은 모두 새 배열의 값에 저장해준다.

 

1. 두 배열 A, B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i, j로 가정한다.

2. i에는 A배열의 시작 인덱스를 저장하고, j에는 B배열의 시작 주소를 저장한다.

3. A[i]와 B[j]를 비교한다. 오름차순의 경우 이중에 작은 값을 새 배열 C에 저장한다.

    A[i]가 더 컸다면 A[i]의 값을 배열 C에 저장해주고, i의 값을 하나 증가시켜준다.

4. 이를 i나 j 둘 중 하나가 각자 배열의 끝에 도달할 때 까지 반복한다.

5. 끝까지 저장을 못한 배열의 값을, 순서대로 전부 다 C에 저장한다.

6. C 배열을 원래의 배열에 저장해준다.

 

이 정렬 알고리즘은 분할 과정과 합병 과정이 나뉘어진다.

 

합병 과정은 두 배열 A, B를 정렬하기 때문에, A배열의 크기를 N1, B배열의 크기를 N2라고 할 경우 O(N1+N2)와 같다.

배열A와 배열B는 하나의 배열을 나눈 배열들이기 때문에 전체 배열의 길이가 N이라고 할 경우 N = N1 + N2이므로 O(N)이라고 할 수 있다.

 

분할 과정은 logN만큼 일어나는데, 이유는 간단하다. 크기가 N인 배열을 분할하면, 한번 분할하면 N/2, N/2 2개, 그 다음 분할하면 N/4, N/4, N/4, N/4 4개.

즉 분할 과정은 매번 반씩 감소하므로 logN만큼 반복해야 크기가 1인 배열로 분할 할 수 있다.

 

각 분할별로 합병을 진행하므로, 합병정렬의 시간 복잡도는 O(NlogN)이다.

사용하는 공간은 정렬을 위한 배열을 하나 더 생성하므로 2N개 사용한다.