정렬2 - 합병정렬(merge sort)

1. 개념

 Merge sort는 분할정복법을 사용하여 정렬하는 알고리즘이다.

1) 분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

2) 정복: 각각의 작은 문제를 순환적으로 해결

3) 합병: 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

2. Pseudocode

merge(A[ ], p, r){    ▷ A[p...r]을 정렬한다.

if(p < r) then {

q ← (p+q)/2;    ---------------① ▷ p, q의 중간 지점 계산

mergeSort(A, p, q);    --------②  ▷ 전반부 정렬

mergeSort(A, q+1, r);  --------③ ▷ 후반부 정렬

merge(A, p, q, r);    -----------④ ▷ 합병

}

}

merge(A[ ], p, q, r){

정렬되어 있는 두 배열 A[p...q]와 A[q+1...r]을 합하여 

정렬된 하나의 배열 A[p...r]을 만든다.

}

3. 시간복잡도

1/2한 Array에 대해 정렬하는데 걸리는 시간 T(n/2), 나머지 반의 Array에 대해 정렬하는데 걸리는 시간 T(n/2) 그리고 Merge하는데 필요한 횟수는 최대 n이다.

$$O(nlogn)$$

4. 소스코드

import java.util.Arrays;

public class MergeSortTest {
	
	public static void mergeSort(int data[], int left, int right){
		if(left < right){
			int mid = (left+right)/2;
			
			mergeSort(data, left, mid);
			mergeSort(data, mid+1, right);
			merge(data, left, mid, right);			
		}
	}
	
	public static void merge(int data[], int left, int mid, int right){
		int i=left, j=mid+1, k=left;
		int tmp[] = new int[data.length];
		
		while(i<=mid && j<=right){
			if(data[i]<=data[j])
				tmp[k++]=data[i++];
			else
				tmp[k++]=data[j++];
		}
		while(i<=mid)
			tmp[k++] = data[i++];
		while(j<=right)
			tmp[k++] = data[j++];
		for(i=left; i<=right; i++)
			data[i] = tmp[i];
	}
	
	public static void main(String[] args) {
		int[] data = {4,2,3,1,5,6,7};
		mergeSort(data, 0, data.length-1);
		System.out.println(Arrays.toString(data));
	}
}