병합 정렬(merge sort)

개념

- 배열을 모두 반으로 쪼갠 후 나중에 두 집합을 묶어서 정렬하는 알고리즘(분할정복) 

- 각 부분 집합은 값이 완전히 정렬이 된 상태

- 기존의 데이터를 담을 추가적인 배열 공간이 필요하다는 점에서 비효율적

	static final int NUMBER = 8;
	int[] sortArray = new int[NUMBER];
	//배열 합치기
	void merge_array(int[] array, int start, int middle, int end) {
		System.out.println("\tstart merge_array");
		System.out.println("\t\tstart: "+start+" middle: "+middle+" end: "+end);
		int i = start;
		int k = start;
		int j = middle+1;
		//배열을 합칠 때, 각 부분 집합을 비교하여 가장 작은 값을 배열에 넣는다.
		while(i <= middle && j <= end) {
			if(array[i] <= array[j]) {
				sortArray[k] = array[i];
				i++;
			}else {
				sortArray[k] = array[j];
				j++;
			}
			k++;
		}
		//집합 중 하나가 먼저 정렬이 완료 된 상태라면, 나머지 집합의 남은 값도 배열에 넣는다.		
		if(i > middle) {
			for (int l=j; l<=j; l++) {
				sortArray[k] = array[l];
				k++;
			}
		}else {
			for (int l=i; l<= middle; l++) {
				sortArray[k] = array[l];
				k++;
			}
		}
		//임시로 저장해둔 값을 실제 정렬을 수행하는 배열로 이동 
		for (int l=start; l <= end; l++) {
			array[l] = sortArray[l];
		}
		System.out.println("\tend merge_array");
	}
	//배열 나누기
	void divide_array(int[] array, int start, int end) {
		System.out.println("divide_array start: "+start+" end: "+end);
		if( start < end ) {
			int middle = (start + end)/2;
			divide_array(array, start, middle);
			divide_array(array, middle+1, end);
			merge_array(array, start, middle, end);
		}
	}

 

※ 시간복잡도 O(N*log N) 

※ 퀵 정렬의 경우, 최악의 경우 O(N^2)이지만 병합정렬은 O(N*log N)을 보장한다.