병합 정렬이란? 재귀를 이용한 정렬방법으로 원래의 배열을 분할한 뒤 정렬하며 병합하는 방식으로 정렬을 수행하는 방법을 말한다. 분할 정복의 개념을 도입한 방법이며, 부분 배열 array [a.... b]를 다음과 같이 정렬한다. 1. 만일 a=b이면 아무것도 하지 않는다. 부분 배열이 원소 한 개로 이루어져 있으며, 이는 이미 정렬되어 있기 때문이다. 2. 가운데 원소의 위치를 k = (a+b)/2 ※이때, a+b가 2로 나누어 떨어지지 않는다면 (a+b)/2보다 크지 않은 정수중 가장 큰 수가 k가 된다. 3. 재귀적으로 부분 배열 array [a.... k]를 정렬한다. 4. 재귀적으로 부분 배열 arrat [k+1..... b]를 정렬한다. 5. 정렬된 부분 배열 array [a... k]와 arr..
