[Algorithm]합병 정렬(Merge Sort)

합병정렬은 정렬을 

분할 : 배열을 반으로 분할한다.

정복 : 분할한 배열을 정렬한다.

합병 : 분할된 정렬들을 합쳐서 정렬한다.

순으로 진행된다.

위의 그림을 참조한다.

위 그림처럼 각각의 두 배열을 정렬하는 것(정복)은 Recursion으로 풀어볼 수 있다.

그리고 합병을 할 때 원래 배열과 같은 크기의 임시배열을 필요로 한다.

i, j, k변수로 배열을 증가를 나타내어 변수가 배열을 끝을 나타내면 불필요한 연산을 막을 수 있다. 

위 그림의 동작순서를 설명하면 arri[i] 와 arrj[j]를 비교하여 A가 H보다 작으니 추가배열 첫번째 요소에 넣고 i를 증가시킨다. 다음으로 G가 H보다 작으니, 다시 i를 증가 추가배열에 넣는다. 다시 L과 H를 비교, H가 작으니 추가배열에 요소를 넣고 요소가 추가 될 때마다 k를 증가시킴으로 정렬된 배열을 모두 합병한다. 

위와 같이 분할은 재귀로, p r은 배열 첫과 끝으로 변수를 둔다.

merge함수이다. 첫번째 while문은 합병정렬을 하며, 두번째 세번째는 while문은 i or j가 배열끝에 이르렀을 때 실행된다. 즉 두번째 세번째 반복문은 둘 중 하나만 실행되는 것이다.

시간 복잡도이다. 풀어보자면 배열요소의 수가 n일 때 n log2 n의 식이 된다.

아래는 코드다.

import java.util.*;

public class Test {

static void Merge(int data[], int p, int q, int r){

int i=p, j=q+1, k=p;

int[] tmp = new int[data.length];

while(i<=q && j<=r){

if(data[i]<=data[j])

tmp[k++]=data[i++];

else

tmp[k++]=data[j++];

}

while(i<=q)

tmp[k++]=data[i++];

while(j<=r)

tmp[k++]=data[j++];

for(i=p; i<=r; i++)

data[i]=tmp[i];

}

static void mergeSort(int A[], int p, int r){

if(p<r){

int q=(p+r)/2;

mergeSort(A,p,q);

mergeSort(A,q+1,r);

Merge(A,p,q,r);

}

}

public static void main(String[] args){

int[] A = {2, 5, 4, 9, 6, 3, 8, 0, 1, 7};

mergeSort(A,0,9);

for(int i=0;i<10; i++)

System.out.println(A[i]);

}

}