병합정렬 (Merge Sort)

시간복잡도

O(nlogn)

vs 퀵 정렬(Quick Sort)

퀵정렬의 경우 최악의 경우 O(n^2)의 시간복잡도를 가지지만 병합정렬의 경우 항상 O(nlogn)의 시간복잡도를 가지므로 퀵정렬보다 빠를거라 생각될 수 있다. 하지만 일반적인경우 퀵정렬이 20% 성능이 더 좋다고 한다. 퀵정렬이 최악의 시간복잡도를 가지려면 정렬된 집합이어야 한다.

로직

배열을 반으로 쪼개서 정렬한 후 다시 합친다(Merge)

재귀를 통해 회귀하면서 병합작업을 한다.

1. 배열을 반으로 쪼개서 각각 재귀 호출을 한다.

2. 기저레벨인 배열이 하나의 원소만 포함하고 있을때 회귀를 시작한다.

3. 회귀하면서 둘로 쪼개진 배열을 서로 비교하면서 또다른 배열에 차례대로 넣는다.

4. 재귀 레벨이 루트로 돌아오면 정렬된 배열을 얻을 수 있다.

JAVA 소스

public static int[] recursiveMerge(int[] inputArr){
		int size = inputArr.length;
		if(size <= 1){
			return inputArr;
		}
		
		int[] dividedArr1 = new int[size/2];
		int[] dividedArr2 = new int[size - (size/2)];
		
		for(int i=0; i<dividedArr1.length; i++){
			dividedArr1[i] = inputArr[i];
		}
		
		for(int i=0; i<dividedArr2.length; i++){
			dividedArr2[i] = inputArr[size/2 + i];
		}
		
		
		int[] resultArr1 = recursiveMerge(dividedArr1);
		int[] resultArr2 = recursiveMerge(dividedArr2);
		
		int[] returnArr = new int[resultArr1.length + resultArr2.length];

		int k = 0;
		int i = 0;
		int j = 0;
		while(k < (resultArr1.length+resultArr2.length)){
			
			if( ( i< resultArr1.length) && ((j >= resultArr2.length) || (resultArr1[i] < resultArr2[j])) ){
				returnArr[k] = resultArr1[i];
				i++;
			}else if(( j < resultArr2.length) && ((i >= resultArr1.length) || (resultArr1[i] >= resultArr2[j])) ){
				returnArr[k] = resultArr2[j];
				j++;
			}
			
			k++;
		}
		
		
		return returnArr;	
		
	}