병합정렬 Merge Sort

병합정렬

데이터를 반으로 나누어 정렬을 수행하는 알고리즘.

분할 정복 알고리즘.

 

수행방식

① 배열을 숫자 1개만 남을 때까지 반복해서 1/2로 나눈다.

② 두 배열씩 결합하며 작은 숫자에서 큰 숫자로 정렬한다.

③ 결합을 반복하며 배열의 크기를 늘려나간다.

 

 

시간복잡도

O(nlogn)

 

구현(JAVA)

 

public class MergeSort {
	
	static int[] arr;
	static int[] tmp;
	public void mergeSort(int start, int end) {
		
		if(start<end) {
			int mid = (start+end)/2;
			mergeSort(start, mid);
			mergeSort(mid+1, end);
			merge(start, mid, end);
		}
		
	}
	private void merge(int start, int mid, int end) {
		
		int a = start;
		int b = mid+1;
		int idx = start;
		
		System.out.println("start : "+start+" end : "+end+" mid : "+mid);
		
        //값을 비교해서 담기
		while(a <= mid && b <= end) {		
			if(arr[a]<=arr[b]) {
				tmp[idx++]=arr[a++];
			}
			else{
				tmp[idx++]=arr[b++];
			}
		}
		
        //어느 한쪽이 먼저 끝난 경우, 남은 쪽을 담아주는 로직
		if(a>mid) {
			while(b<=end) {
				tmp[idx++] = arr[b++]; 
			}
		}else {
			while(a<=mid) {
				tmp[idx++] = arr[a++]; 
			}
		}
		
		
		
		for(int i = start; i<=end; i++) {
			arr[i] = tmp[i];
		}
	}
	
	public static void main(String[] args) {
		arr = new int[] {5, 2, 4, 1, 6, 3};
		tmp = new int[arr.length];
		MergeSort f = new MergeSort();
		f.mergeSort(0, arr.length-1);
		System.out.println(Arrays.toString(arr));
		
	}

}

출처

• 컴퓨터 알고리즘 기초 5강 합병정렬, T아카데미