병합정렬(Merge Sort)

전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬 방식.

1. 분할

 아래 그림과 같이 배열 집합을 하나의 원소 단위로 각각을 분할한다.

2. 병합

  분할된 각각의 원소에 대해 서로의 쌍을 비교하여 sorting 후 병합한다.

3. Sorting 과정.

병합시의 Sorting 과정을 살펴보면 우선 병합하려고 하는 크기의 메모리를 할당한 다음, 두 개의 원소에 대해 각각을 비교하여 할당된 메모리에 집어넣는다.

그림을 보며 설명하는게 더 나을지도..

1. 0,3,8 과 1,2,4에 대한 병합 작업이 이루어지고 있다. 두 배열을 합치면 총 6의 공간이 필요하기 때문에

6의 메모리 배열을 새롭게 만들어 두고 작업을 진행한다. 각 배열의 제일 왼쪽 원소부터 서로 비교한다. 

두 개의 원소 중 작은 값을 메모리 배열에 집어넣고 메모리에 들어간 배열은 인덱스를 1증가시킨다.

위의 그림에서 보면 0이 1보다 작기 때문에 0이 메모리에 들어가고 인덱스가 하나 증가되어 3을 가리키게 되었다.

2. 3과 1을 비교한다. 1이 더 작으므로 1이 메모리에 들어가고, 인덱스는 2를 가리킨다. 2또한 3보다 작으므로 메모리에 들어가고 인덱스는 4를 가리키게 된다.

3. 이런식으로 병합할 때마다 Sorting을 하면 최종 정렬된 결과를 확인할 수 있다.