[알고리즘] 병합 정렬(Merge Sort)

병합 정렬

n개의 정렬되지 않은 데이터들이 들어있는 배열에서

1번째부터 n/2번째까지, n/2+1번째부터 n번째까지의 데이터를 2개의 배열로 나누고

이 나누어진 배열을 다시 1번째부터 (n/2)/2번째까지, (n/2)/2+1번째부터 n/2번째까지의 2개의 배열과

(n/2)+1번째부터 (n/2)+1 + (n/2)/2번째까지, (n/2)/2+1 + (n/2)/2+1번째부터 n번째까지 2개의 배열로 나눈다.

이러한 과정을 계속 반복하여

각각의 array의 길이가 1이하가 될 때 까지 n개의 데이터가 들어있는 1개의 배열을 k개의 부분배열로 나눈다.

그리고 잘게 쪼개어진 배열들을 2쌍씩 묶어서 정렬한다.

쉽게 말해서, 큰 문제를 여러 개의 작은 문제들로 쪼개어 처리하는 Divide and Conquer기법을 사용한다.

public static int[] mergeSort(int[] array){

if(array.length<= 1){

return array;

}

int mid= (array.length-1)/2;

int[] a1= mergeSort(getSubArray(array, 0, mid));

int[] a2= mergeSort(getSubArray(array, mid+1, array.length-1));

int result[]= new int[a1.length+ a2.length];

int a1_index= 0;

int a2_index=0;

int result_index=0;

while(a1_index<= a1.length-1 && a2_index<= a2.length-1){

if(a1[a1_index]< a2[a2_index]){

result[result_index]= a1[a1_index];

result_index++; 

a1_index++;

}else{

result[result_index]= a2[a2_index];

result_index++; 

a2_index++;

}

}

while(a1_index<= a1.length-1){

result[result_index]= a1[a1_index];

result_index++; 

a1_index++;

}

while(a2_index<= a2.length-1){

result[result_index]= a2[a2_index];

result_index++; 

a2_index++;

}

return result;

}

public static int[] getSubArray(int array[], int start, int end){

if(start<0 || end>= array.length){

System.out.println("ArrayOutOfIndex");

System.exit(-1);

}

int[] result= new int[end- start+1];

for(int i=0; i<result.length; i++){

result[i]= array[start+i];

}

return result;

}

다른 Sort알고리즘과는 다르게 best case건 worst case건 input갯수가 같다면 비교 횟수도 동일하다.

n개의 데이터들을 원소가 1개일 때 까지 분할하는 과정에서,  depth가 log₂n 인 분할 과정을 거친다.

이제 분할된 배열들을 병합(merge)하는 과정에서, 매 병합 과정마다 k번(나누어진 두개의 배열의 길이의 합)의 비교를 거친다.

이 병합 과정을 depth를 알아볼 수 있는 트리로 살펴보면, 매번의 depth마다 n번의 비교가 일어난 다는 것을 알 수 있다.

간단히 표현해 보면

1 2 3 4 // 분할 시작

(1 2) (3 4) //첫 번째 분할

(1) (2) (3) (4) //분할 끝.

(1 2) (3 4) // 첫 번째 병합. (1) (2)를 합치고, (3) (4)를 합치는데 총 2+2 (n= arrayLength= 4)번을 비교했다

1 2 3 4 // 두 번째 병합. (1 2)와 (3 4)를 합치는데 총 4번을 비교했다.

병합이 일어날 때, depth가 바뀔 때 마다 n번의 비교가 일어난다는 것을 알 수 있다.

그렇다면 depth를 알아내면 되는데, 분할 횟수가 log₂n 번 이므로, depth도 log n이 된다.

따라서 Time Complexity는 O(n*log n)이 된다.

Time Complexity에 관해서는 다른 Sort 방법보다 현저히 낮은 수치를 보여주지만

배열을 분할하고 합치는 과정에서 상당히 많은 메모리를 잡아먹을 수 있다는 단점이 있다. (높은 Space Complexity)

따라서 메모리가 충분하지 않은 환경에서의 Merge Sort는 부적합하다.