|머지정렬 개념 | 머지정렬 알고리즘| 머지정렬 분석 |

▷ 원소의 개수가 각각 m,n인 두 배열을 합병하기 위하여는 최악의 경우에 m+n-1회의 비교

▷ 두 부분 배열의 크기가 같고 이를 m이라 할 때, 최악의 경우에 2m-1회의 비교

▷ n개의 원소로 구성된 배열에 머지 정렬을 적용하면 그 실행 시간은 n/2개의 원소로 된
           두 개의 부분 배열을 정렬하는 시간과 이들을 합병하는 데 드는 시간의 합으로 O(nlogn)

▷ 머지 정렬에서는 동일한 두 키의 상대 위치가 정렬 과정에서 변하지 않으므로 안정적이나,
           합병하는 과정에서 입력 배열의 크기만큼의 메모리 공간이 요구되므로 제자리 정렬은 아님