[합병(병합)정렬 (Merge Sort)] 머지소트는 폰 노이만(John von Neumann)이 1945년 개발한 알고리즘이다. 원소들간의 비교을 통하여 정렬하는 비교기반정렬 알고리즘이다. 원소들 중에 같은 값이 있는 경우 정렬후에도 이들의 순서가 유지되는 안정 정렬에 속한다. N개의 데이터를 정렬할 때, 시간복잡도는 O(N * logN)이 보장된다. 정렬의 각 과정은 분할 -> 정복 -> 결합과정으로 이루어진다. [합병정렬(오름차순) 알고리즘 프로세스] 정렬할 배열을 A[], 구간의 시작 인덱스(배열번호)를 low, 끝 인덱스를 high 라고 하자. 1. low >= high 라면 현재 구간은 정렬된것으로 본다. 그렇지 않은 경우 2. 분할(Divide) 과정 : 구간의 중앙을 구한다. mid = (..
