합병 정렬 - Merge sort (java)

정의

Merge Sort (합병 정렬)이란 ?

안정정렬 , 분할 정복 알고리즘의 일부중 하나
해결하기 어려운 문제를 작은 문제(Fractal) 문제로 쪼개어 천천히 정복해 나가는 알고리즘입니다.
MergeSort는 퀵 정렬과 달리, 데이터의 크기 만큼 추가적인 공간을 필요로 하기에
"제자리-정렬"이 될 수 없다.
=> 제자리 정렬이 아니기에 Memory를 많이 먹을 수도 있다.

정렬 알고리즘

알고리즘	최소 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도	공간복잡도
병합정렬	O(NlogN)	O(NlogN)	O(NlogN)	O(n)

Merge Sort는 언제나 동일한 시간복잡도를 같습니다.
이에 따라 크기가 큰 리스트를 정렬함에 있어서 유리한 편입니다.

Merge Sort의 정렬 과정

합병 정렬의 핵심을 아래와 같습니다.

분할 : 배열을 2개의 리스트를 분할합니다
정복 : 분할된 리스트를 정렬합니다
결합 : 분할된 두 개의 리스트를 하나의 리스트로 결합합니다.

1. 분할 - 분할된 리스트 1개의 요소만 남을 때까지 분할합니다.
2. 정복 - 분할된 2개의 리스트를 놓고 정렬합니다
3. 결합 - 정렬된 2개의 리스트를 결합하여 , 하나의 리스트로 반환합니다
4. 반복 - 분할된 모든 리스트가 하나의 리스트가 될 때까지 이를 반복합니다

두 개의 리스트 합병 과정

두 개의 리스트를 하나의 리스트로 만드는 과정에서 시간복잡도는
두 리스트의 크기를 합친 시간만큼 발생하게 됩니다.

차례대로 각각의 Index에 선택된 요소들을 비교해가며 리스트를 만들어 나갑니다.

한 쪽의 리스트가 마지막 인덱스까지 결합된 리스트에 담기게 되면,
다 담기지 못한 리스트의 남은 요소들을 뒤에 붙이면 됩니다.
* 아래는 참고 사진입니다

Java 구현하기

public class MergeSort {
	public static int[] sort(int[] arr){
    	// 배열의 크기가 1이면 그대로 반환
    	if (arr.length < 2) return arr;
        
        // 배열의 중간 index값
        int mid = arr.length / 2;
        
        // arr의 배열을 둘로 쪼개어 왼쪽은 low_arr / 오른쪽은 high_arr => python의 슬라이싱과 비슷한 동작
        int[] low_arr = sort(Arrays.copyOfRange(arr,0,mid));
        int[] high_arr = sort(Arrays.copyOfRange(arr,mid,arr.length));
        
        // 두 리스트에서 뽑아서 결합할 배열 생성
        int[] mergedArr = new int[arr.length];
       	int m = 0, l = 0, h = 0;   // 각각 배열의 인덱싱 변수
        
        while (l < low_arr.length && h < high_arr.length){
        	if (low_arr[l] < high_arr[h])
            	mergedArr[m++] = low_arr[l++];
            else
            	mergedArr[m++] = high_arr[h++];
        }
        
        // 두 배열에 남아있는 요소들을 뒤에 붙입니다.
        while (l < low_arr.length) {
            mergedArr[m++] = low_arr[l++];
        }
        while (h < high_arr.length) {
            mergedArr[m++] = high_arr[h++];
        }
        return mergedArr;
    }
}

마무리하며

Merge sort는 항상 동일한 시간을 유지하지만 추가적인 공간을 필요로 합니다.
이를 충분히 고려하면서 사용하기 적절한지 항상 판단하는 것을 고려하고
아래에 이해를 더 편하게 돕기위해 관련 영상을 올려놓겠습니다.

참고 영상

https://youtu.be/ZRPoEKHXTJg
"Timo Bingmann" by Youtube