[알고리즘] 합병정렬(Merge Sort) - JAVA

합병정렬(Merge Sort)

• 주어진 배열 또는 리스트의 길이가 1이 될 때까지 분할한 뒤, 부분 배열을 정렬하면서 합치는 정렬이다.
  • 배열의 길이가 1이 될 때(하나의 원소만 가진 상태)까지 분할한다. - 분할(divide)
  • 1이 되면 길이가 짧은 것부터 부분배열을 정렬한다. - 정복(conquer)
  • 정렬된 배열끼리 합친다. - 결합(combine)
  • 정복과 결합을 반복하다 부분배열이 1개 남으면 정렬된 전체 배열이 된다.
• 병합 정렬이라고도 한다.
• 시간복잡도는 O(nlogn)로 일정하다.
  • 분할이 트리형태(6개의 원소를 가진다면 6->3->1)로 이루어지기 때문에 합치는 과정에서 깊이가 log²n이 되고,  원소의 대소 비교횟수는 합치는 과정마다 원소를 다 보게 되므로 n번이 된다. 따라서 시간복잡도는 O(n*log²n) = O(nlogn)이 된다.
• 제자리 정렬이 아니다. (입력받은 배열외에 다른 메모리가 필요하다.)
  • 합병할 때, 합병한 결과를 담을 배열이 필요하다.
• 안정 정렬 (=동일한 값에 대해 순서가 바뀌지 않는다.)

 

 

배열[6,3,4,1,5,2]가 있을 때, 합병정렬로 정렬하는 과정

 

 

 

[구현코드 - JAVA]

public class MergeSort {
	public static int[] tmp;
	
	public static void main(String[] args) {
		int[] arr = {6,3,4,1,5,2};
		tmp = new int[arr.length];

		merge_sort(arr,0,arr.length-1);
		//정렬 후
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]+" "); //1 2 3 4 5 6
		}
	}
	
	
	public static void merge_sort(int A[], int start, int end) { // A[start..end]을 오름차순 정렬한다.
		//길이가 1이 될 때까지 분할
		if (start < end) {
	        int mid = (start + end) / 2;      // start와 end의 중간지점
	        merge_sort(A, start, mid);      // mid를 중심으로 왼쪽 분할
	        merge_sort(A, mid + 1, end);  // mid를 중심으로 오른쪽 분할
	        merge(A, start, mid, end);        // 정복 및 결합 
	    }
	}

	//A[start..mid]와 A[mid+1..end] 합병
	public static void merge(int A[],int start,int mid,int end) {
	    int i = start;
	    int j = mid + 1;
	    int t = 0;
	    
	    //배열A에서 비교하고 작은 쪽 배열tmp에 저장
	    while (i <= mid && j <= end) {
	        if (A[i] <= A[j]) { //배열A의 i번째 배열tmp에 저장
	        	tmp[t++] = A[i++]; //i번째 저장하고 다음 t, i로 넘어감
	        }
	        else { //배열A의 j번째 배열tmp에 저장
	        	tmp[t++] = A[j++]; //j번째 저장했으므로 다음 t, j로 넘어감
	        }
	    }
	    while (i <= mid)  //왼쪽 배열 부분이 남은 경우
	        tmp[t++] = A[i++];
	    while (j <= end)  //오른쪽 배열 부분이 남은 경우
	        tmp[t++] = A[j++];
	    
	    i = start;
	    t = 0;
	    while (i <= end) { //tmp에 저장한 결과를 A[start..end]에 저장
	        A[i++] = tmp[t++];
	    }
	}
}