[Algorithm] 병합정렬에 대해 알아보자 !! 😎

◾ 병합정렬

여러개의 정렬된 자료의 집합을 병합해 한개의 정렬된 집합으로 만드는 방식

 

분할 정복 알고리즘 활용해 문제 해결

• 자료를 최소 단위 문제까지 나눈 후 차례대로 정렬해 결과를 얻음
• top-down
• 안정 정렬

분할 정복 알고리즘 이란 ???
 > 문제를 더 작은 2개의 문제로 분리하고 각각을 해결한 결과를 모아서 원래의 문제를 해결하는 전략

 

시간 복잡도

• O(n log n)

 

병합 정렬 과정

 

이해를 돕기 위해 사진으로 먼저 정리하자면 다음과 같다.

 

 

이미지 출처 : https://st-lab.tistory.com/233

 

병합하는 과정이 헷갈렸는데, 위의 이미지를 보고 이해하게 되었다.

 

• 하나의 큰 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 이러한 병합 정렬은 크게 두가지 단계로 구분할 수 있다.
  1. 분할 : 전체 자료 집합에 대해 최소 크기의 부분 집합이 될 때까지 같은 크기의 2개의 부분 배열로 분할
  2. 병합 : 2개의 부분 집합을 정렬하면서 하나의 집합으로 병합

 

◾ 병합 정렬 알고리즘

수도 코드를 통해 알고리즘을 이해한 후에 JAVA로 구현해 보는 것을 추천한다 !

 

// 1. 분할
mergeSort(arr[], left, right) {
	IF left < right :
    	mid = (left + right) / 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, right)
        merge(arr, left, mid, right)
}

// 2. 병합
merge(arr[], left, mid, right) {
	L = left, R = mid + 1, idx = left
    
    WHILE L <= mid && R <= right {
    	IF arr[L] <= arr[R] :
        	sortedArr[idx++] = arr[L++]
        ELSE
        	sortedArr[idx++] = arr[R++]
    }
    
    IF L <= mid {
    	FOR i IN L TO mid :
        	sortedArr[idx++] = arr[i]
    } ELSE {
    	FOR j IN R TO right :
        	sortedArr[idx++] = arr[j]
    }
    
    FOR i IN left TO right
    	arr[i] = sortedArr[i]
}