[자바] 정렬 알고리즘 - 병합 정렬

앞서 있었던 퀵정렬은 피벗 값에 따라서 편향되게 분할 될 가능성이 있다는 것이다 그래서 최악의 경우 O(N^2)의 시간 복잡도를 가진다. 

하지만 지금 배울 병합정렬은 편향되게 분할 될 가능성이 없다. 정확히 반 반씩 나누기 때문에 최악의 경우에도 O(N*logN)의 시간복잡도를 보장한다.

 

Divdie and Conquer방식이라고도 배우는데

병합정렬

먼저 기존에 있는 배열들을 작게 작게 각각 하나씩 가질때 까지 나눈다는 것이다 그리고 merge할때 정렬해가면서 합친다는 것이다. 

정렬을 할때 다른 배열을 생성하여 그 배열에 정렬해서 넣는것이다 

방법은 나뉘어진 배열 2개에 대해 합치게 되는데 이때 각각 배열의 첫번째 인덱스의 값들을 비교해서 작은 것부터 생성한 배열에 넣는것이다.

구체적 사진

 위의 그림처럼 말이다

 

코드를 살펴보자

public class MergeSort {
	
	private static int[] sorted;
	
	public static void sort(int []a) {
		sorted=new int[a.length];
		divideandconquer(a,0,a.length-1);
		sorted=null;
	}
	
	private static void divideandconquer(int []a, int left,int right) {
		int mid;
		if(left<right) {
			mid=(left+right)/2;
			
			divideandconquer(a,left,mid);
			divideandconquer(a,mid+1,right);
			
			merge(a,left,mid,right);
		}
	}
	
	private static void merge(int []a, int left,int mid,int right) {
		int l=left;
		int r=mid+1;
		int idx=left; //새로운배열에 넣기 위함
		
		while(l<=mid && r<=right) {
			if(a[l]<=a[r]) {
				sorted[idx]=a[l++];
			}else {
				sorted[idx]=a[r++];
			}
			idx++;
		}
		
		if(l>mid) {
			while(r<=right) {
				sorted[idx++]=a[r++];
			}
		}else {
			while(l<=mid) {
				sorted[idx++]=a[l++];
			}
		}
		
		for(int i=left; i<=right; i++) {
			a[i]=sorted[i];
		}
		
		
	}
}

여기에서

divideandconquer(a,left,mid);
divideandconquer(a,mid+1,right);

//밑의 코드는 오류가 난다
divideandconquer(a,left,mid-1);
divideandconquer(a,mid,right);

오류가 나는 원인은 스택오버플로우이다.

 

장점

항상 두 부분리스트로 쪼개어 들어가기 때문에 최악의 경우에도 O(NlogN)이 유지가 된다.

 

 

단점

- 정렬과정에서 추가적인 보조 배열 공간을 사용하기 때문에 메모리 사용량이 많다. 

- 보조 배열에서 원본배열로 복사하는 과정에 의해 데이터가 많을경우 상대적으로 시간이 많이 소요된다.

 

시간복잡도

내가 정리한 것