Merge Sort ( 합병 정렬 )

## 개념 요약 ##

• 일반적인 방법으로 구현했을 때 이 정렬은 "안정 정렬"에 속하며, 분할 정복 알고리즘 중의 하나 이다.
  • 분할 정복 ( divide and conquer ) 방법
    • 문제를 작은 2개의 문제로 분리하고, 각각을 해결한 다음 ! 결과를 모아서 원래의 문제를 해결하는 전략이다.
    • 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
  • 과정 !
    1. 리스트의 길이가 0 or 1 이면, 이미 정렬된 것으로 본다. 1이상이면 ? 
    2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 개로 나눈다.
    3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
    4. 두 리스트를 다시 하나의 정렬된 리스트로 합병한다

## 구체적인 개념 ##

• 하나의 리스트를 2개의 균등한 크기로 분할하고, 분할된 리스트를 정렬, 2개의 정렬된 리스트를 합해 전체가 정렬된 리스트가 되게 하는 방법이다.
• 합병 정렬은 다음의 단계들로 이루어진다.
  • 분할 ( Divide ) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할.
  • 정복 ( Conquer ) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면, 순환 호출을 이용하여 다시 분할 정복을 적용.
  • 결합 ( Combine ) : 정렬된 부분 배열들을 하나의 배열에 합병.\
• 합병 정렬의 과정
  • 추가적인 리스트 필요. ( tmp[] 배열 )
  • 각 부분 배열을 정렬할 때도, 합병 정렬을 순환적으로 호출하여 적용.
  • 합병정렬에서 실제로 정렬이 이루어지는 시점은 , 2개의 리스트를 merge 하는 단계이다.

## 알고리즘 예제 ##

• 배열에 27, 10, 12, 20, 25, 13, 15, 22 가 저장되어있다고 가정하고 오름차순으로 정렬해본다.
• 2개의 정렬된 리스트를 합병(merge)하는 과정
  • 2개의 리스트 값들을 처음부터 하나씩 비교하여 , 2개의 리스트 값 중 더 작은 값을 새로운 리스트로 옮긴다.
  • 둘 중 하나가 끝날 때 까지 이 과정을 되풀이 한다.
  • 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면, 나머지 리스트의 값 들을 전부 새로운 리스트로 복사한다.
  • 새로운 리스트를 원래의 리스트로 옮긴다.

## 알고리즘의 특징 ##

• 단점
  • 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
    • 제자리 정렬(in-place sorting)이 아님..
  • 레코드의 크기가 큰 경우에는, 이동 횟수가 많으므로 매우 큰 시간 낭비를 하게됨.
• 장점
  • 안정적인 정렬 방법
    • 데이터의 분포에 영향을 덜 받음. 즉 , 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일. O(nlog2n) 로 동일.
    • 만약 레코드를 linked list 로 구성하면, 링크 인덱스만 바뀌므로, 데이터의 이동을 무시할 정도로 작아짐.
      • 제자리 정렬로 구현 가능.
    • 따라서, 크기가 큰 레코드를 정렬할 경우에, 연결 리스트를 사용한다면, merge sort 는 퀵 정렬을 포함한 다른 어떤  정렬 방법보다 효율적이다.

## 시간 복잡도 ##

오,,,,,음.....엄...... 어렵당.....우선, 분할 단계와 합병 단계가 있다.

분할 단계 -> 비교 연산과 이동 연산이 수행되지 않음 ! 

합병 단계 -> 합병단계에서 비교 회수가 count됨. 

깊이와 너비로 구분하는데,

1.

순환 호출의 깊이 ( merge 단계 )는,

레코드의 개수 n이, 2의 거듭제곱(n = 2^k)이라고 가정했을 때, 

n  = 2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3... 

일반화 하면, n=2^k의 경우, k=log2n임을 알 수 있드아..

2.

각 합병 단계의 비교 연산 (Width)

크기 1인 부분 배열 2개를 합병하는데는 최대 2번의 비교 연산 필요, 

부분 배열의 쌍이 4개이므로 2*4=8번의 비교 연산 필요.

다음 단계에서는 크기가 2인 부분배열 2개를 합병하는데 4번의 연산이 필요, 부분배열의 쌍이 2개이므로 4*2=8번.

마지막엔, 크기 4인 배열 2개를 합병하는 데는, 최대 8번의 연산이 필요. 부분 배열 쌍이 1개이므로... 8*1 = 8 번.

이걸 일반화 하면, 하나의 합병 단계에서는 최대 n번의 비교연산을 수행함을 알 수 있다.

** 순환 호출 깊이 * 각 합병 단계 연산 = nlog2n

* 이동 횟수 

순환 호출의 깊이 : k = log2n

각 합병 단계의 이동 연산 : 임시 (tmp[]) 에 복사했다가 다시 가져와야 되므로, 총 배열에 들어있는 값의 개수가 n인 경우, 레코드의 이동이 2n번 발생한다.

* 순환 호출 깊이 * 각 합병단계의 이동 연산 = 2nlog2n

* T(n) = nlog2n(비교) + 2nlog2n(이동) = 3nlog2n = O(nlog2n)