[알고리즘] 병합정렬

목차

병합정렬의 개념

1. 병합정렬의 방식
2. 병합정렬의 장단점
3. 병합정렬의 코드구현(JAVA)

병합정렬의 개념

• 병합정렬은 분할정복방식을 사용해서 데이터를 분할하고 분할한 집합을 정렬하며 합치는 정렬.

        분할정복방식:  큰 문제를 작은 문제로 쪼개어서 푼 후 합쳐서 전체 문제의 답을 찾는 방식.

병합정렬의 방식

병합정렬의 장단점

장점

• 병합 정렬은 최선의 경우에도, 최악의 경우에도 O(nlog₂n)의 시간이 소요되기 때문에 데이터 분포에 영향을 덜 받는다. 항상 동일한 시간이 소요되므로 어떤 경우에도 좋은 성능을 보장받을 수 있다.

단점

• 병합 정렬은 in place 알고리즘이 아니기 때문에 별도의 메모리 공간이 필요하다. 만약에 정렬할 데이터의 양이 많은 경우에는 그만큼 이동 횟수가 많아지므로 시간적인 낭비도 많아지게 된다.

병합정렬의 구현(JAVA)

public class MergeSort {
	
	static int[] buff;
	
	static void mergeSort(int[]arr) {
		
		buff = new int[arr.length];
		mergeSort(arr, 0, arr.length-1);
	}
	
	static void mergeSort(int[]arr,int left, int right) {
		
		if(left<right) {
			int center = left + (right-left)/2;
			mergeSort(arr, left, center);
			mergeSort(arr, center+1,right);
			merge(arr,left, center, right);
		}
	}
	
	static void merge(int[]arr, int left,int center,int right) {
		
		int p =0;
		int j=0;
		int k = left;
		int i;
		
		for(i=left;i<=center;i++) {
			buff[p++] = arr[i];
		}
		while(i<=right && j<p) {
			arr[k++] = (buff[j]<=arr[i])? buff[j++] :arr[i++];
		}
		System.out.println(Arrays.toString(arr));
		while(j<p) {
			arr[k++] = buff[j++];
		}
		System.out.println(Arrays.toString(arr));
	}
	
	public static void main(String[] args) {
		int [] arr = {10,3,1,2,6,7,4,9};
		mergeSort(arr);
		System.out.println(Arrays.toString(arr));
	}
}