병합 정렬(Merge Sort)

병합 정렬이란?

배열의 요솟수가 2개 이상인 경우,

배열을 반으로 나눠 앞부분을 병합 정렬하고 뒷부분을 병합 정렬한 후,

앞부분과 뒷부분을 병합하는 정렬 알고리즘.

 

여기서 병합이란 단순히 합치는 것이 아니라, 다음과 같이 이미 정렬된 두 배열의 요소 중 더 작은 요소를 선택해 목표 배열에 넣는 것이다.

 

이미 정렬된 두 배열 병합하기

static void mergeArray(int[] a, int[] b, int[] c) {
    //각 배열의 포인터를 모두 0으로 초기화
    int pa, pb, pc;
    pa=pb=pc=0;
	
    //두 배열의 포인터가 모두 각 배열의 끝에 닿지 못했을 때
    while(pa<a.length && pb<b.length) {
        //두 배열 중 어느 쪽의 값이 작은지 판별해서 목표 배열에 넣는다.
        c[pc++] = (a[pa]>=b[pb]) ? b[pb++] : a[pa++];
    }
	
    //B배열의 포인터는 끝에 닿았지만 A배열 포인터는 닿지 못했을 때
    while(pa<a.length) {
        c[pc++] = a[pa++];
    }
	
    //A배열의 포인터는 끝에 닿았지만 B배열 포인터는 닿지 못했을 때
    while(pb<b.length) {
        c[pc++] = b[pb++];
    }
}

 

자바에서 구현하기