그림으로 알아보는 병합 정렬 (merge sort)

병합 정렬

병합정렬이란, 이미 정렬된 두 개의 배열에 대해 

합쳐진 정렬된 배열을 얻는 방법이다.

결과가 들어갈 새로운 배열을 선언하고,

두 배열의 앞쪽을 비교하면서 결과 배열의 앞쪽부터 채워 넣으면,

쉽게 합쳐진 배열을 얻을 수 있다.

정렬되지 않은 상태에서의 병합정렬

정렬되지 않은 배열 arr[]에 대하여,

arr[]을 균등하게 반으로 나눈 배열을 A[], B[]라고 하자.

여기서 2가지 선택지가 있다.

• A[], B[]를 다른 알고리즘으로 정렬하고 병합정렬로 합친다.

• A[], B[]에 다시 위의 작업을 반복한다.

첫 번째) 

A[], B[]를 퀵 정렬같은 다른 알고리즘으로 정렬하면,

두 개의 배열은 정렬된 상태가 되기 때문에,

이 두 배열을 병합정렬로 합치면 정렬된 arr[]이 완성된다.

두 번째)

다시 A[]와 B[]를 반으로 쪼개고 

각각에 대해 재귀적으로 병합정렬을 실시한다.

정렬 알고리즘에서 길이가 0 또는 1인 배열은 정렬된 상태로 보기 때문에,

부분배열 2개가 정렬되어있는 상황이 반드시 나오기 때문이다.

아래의 그림에서 맨 하단에 있는

길이가 1인 배열들은 모두 정렬된 상태로 본다.

결과적으로 정렬되지 않은 배열은 

정렬된 부분배열들의 합으로 표현될 수 있으므로,

정렬된 각각의 부분배열을 병합하면

정렬된 전체배열을 얻게된다.

k-way 병합정렬

k개의 정렬된 부분배열을 병합하는 것을 

k-way 병합정렬이라고 한다.

아래는 3-way 병합정렬 과정의 일부분이다.

병합정렬의 시간복잡도

여기서 시간복잡도는 병합정렬만을 사용했을 때를 가정한다.

정렬되지 않은 배열을 정렬할 때, 

우선 크기가 1인 배열이 되도록 나누고 2개씩 쌍을 묶어 병합을 실시하므로,

분할과정 : log(n) 

병합과정 : n  

모든 분할에 대하여 병합이 이루어지므로 복잡도는 곱셈으로 이루어진다.

즉, 복잡도는 O( n*log(n) ).

퀵 정렬과 달리 모든 상황에서 시간 복잡도가 동일하다.

코드

버퍼없는 병합 정렬 (in-place merge sort)

버퍼 배열을 만들지 말고,

한 배열 안에서만 병합정렬을 할 수 있지 않을까?

물론 가능하지만, 성능이 O(n^2)으로 떨어진다.

차라리 메모리를 더 쓰는 편이 낫다. 

자세한 내용은 여기를 참조하길 바란다.