1. 합병 정렬(Merge Sort)?
합병 정렬은 작은 구간들을 정렬된 상태로 합병해나가면서, 구간의 크기를 키워가면서 정렬하는 알고리즘입니다.
1.1 어떻게 두 구간을 합병하는가?
두 구간은 각각 이미 정렬된 상태이기 때문에 두 구간을 합병할 때 두 구간은 일종의 스택(Stack)으로써 맨 앞에는 각 구간의 최소값을 갖는 원소가 들어있게 된다. 이 최소값을 비교하여 둘 중 작은 값을 꺼내주기(pop)를 반복하면, 두 구간의 원소들이 정렬된 상태로 합병되게 한다.
두 구간의 합병 과정을 예를 통해 표현하면 다음과 같다.
2. 예시
3
|
8
|
7
|
1
|
5
|
데이터를 가지고 직접 합병 정렬을 해봅시다.
1. 구간을 설정한다.
3
|
8
|
7
|
1
|
5
|
3
|
8
|
7
|
1
|
5
|
3
|
8
|
1
|
7
|
5
|
3
|
8
|
1
|
7
|
5
|
1
|
3
|
7
|
8
|
5
|
1
|
3
|
5
|
7
|
8
|
1
|
3
|
5
|
7
|
8
|
위 의 코드의 경우, 매번 합병할 때마다 구간내 원소를 복사해서 합병을 하기 때문에 속도가 느려진다. 하지만, 포인터로 합병할 원소들이 있는 주소와 합병된 원소들이 있는 주소를 조작해주면 복사하는 과정이 없어지기 때문에 속도가 향상된다. 다만, 이 때 결과값이 최종적으로 원래의 배열에 들어가도록 주의하여야한다.
다음은 포인터를 이용하여 합병시마다 반복되는 복사과정을 없앤 합병 정렬이다.
