[자료구조/sort] 병합정렬 (Merge Sort)

내 생각에 버블,선택,삽입정렬 정도는 아무런 참고 없이 손코딩 할줄 아는게 좋다고 생각하지만, 

머지소트부터는 손코딩 하기도 힘들뿐더러 그럴필요도 없다 

왜냐하면 어차피 이런것들은 아주 잘짜여진 미리 만들어져있는 코드들이 수많이 존재하기 때문이다.

그렇기 때문에 머지소트의 동작과정과 빅오, 어떤 경우에 사용해야 좋은지, 장단점 등등만 잘 알아놓는게 중요한것 같다.

그래야 상황에 맞는 자료구조를 잘 선택할수 있게 될것이다.

머지소트의 동작과정은 다음과 같다.

이 그림에서 처럼 하나의 배열을 반으로 계속해서 자르면서 마지막에 원소가 1개일떄까지 계속 잘라나간다.

그리고 난뒤, 잘라진 조각들이 합쳐지면서 정렬이 완료되게 되는데, 

위의 코드는 분할을 하는 과정을 나타낸것이다. 보면 알겠지만 재귀를 통해서 계속해서 배열을 반반으로 자르고 있다.

위에서부터 계속 반으로 잘라 내려가다가 마지막에 first==last가 되는순간(배열의 원소가 1개일떄) 합병을 시작하게 된다.(merge함수)

정복하는 코드는 다음과 같다.

  while (i <= middle && j <= n) {
            if (arr[i] <= arr[j])
                sorted[k] = arr[i++];
            else
                sorted[k] = arr[j++];
            k++;
        }

위 예제에서 10 12 20 27 과 13 15 22 25를 합친다고 가정해보자.

middle에 해당하는 숫자는 27일것이고 i는 10~27을 j는 13~25를 탐색하게 된다.

두 개의(arr[i],arr[j]) 배열 중에서 각각 하나씩 꺼내서 둘중 작은것을 새롭게 만든 배열(sorted[k])에다가 작은 순서대로 넣는다.

그렇게 될경우 

1. 왼쪽 배열의 숫자는 모두 sorted에 옮겼는데 아직 오른쪽 배열의 숫자가 남아있는 경우가 생길수가 있고,

2. 오른쪽 배열의 숫자는 모두 sorted에 옮겼는데 아직 왼쪽 배열의 숫자가 남아있는 경우가 생길수가 있다.

그것을 해결해주기 위한 코드가 바로 밑에 나와있다.

if (i > middle) 
{
    for (t = j; t <= n; t++, k++)
         sorted[k] = arr[t];
} 
else 
{
    for (t = i; t <= middle; t++, k++)
          sorted[k] = arr[t];
}

if(i>middle)이란것은 왼쪽 배열의 숫자를 모두 sorted에 옮겼다는 뜻이다. 그런경우? 오른쪽 배열의 남은 숫자를 모두 sorted에 옮겨야 한다(for문)

else에 걸린경우  i<=middle 이란 뜻인데 이것은 다르게 말하면 왼쪽 배열엔 숫자가 남아있는데 오른쪽 배열의 숫자를 모두 sorted에 옮겼다는 뜻이므로

남아있는 왼쪽배열을 마저 sorted에 옮겨야 한다. 

이처럼 머지소트는 분할 정복 과정중 정복의 과정에서 새로운 배열이 필요하므로 추가적인 메모리 공간이 필요하다는 단점이 있으나, 

메모리 공간은 시간에 비해 대체적으로 관용적인 편이다.

자바로 구현한 머지소트는 다음과 같다.

package Merge;
 
import Selection.SelectionSort;
 
public class MergeSort {
    public static int[] sorted = new int[30];
 
    public static void mergeSort(int[] arr, int m, int n) {
        int middle;
        if (m < n) {
            middle = (m + n) / 2;
            mergeSort(arr, m, middle);
            mergeSort(arr, middle + 1, n);
            merge(arr, m, middle, n);
        }
    }
 
    public static void merge(int[] arr, int m, int middle, int n) {
        int i, j, k, t;
 
        i = m;
        j = middle + 1;
        k = m;
 
        while (i <= middle && j <= n) {
            if (arr[i] <= arr[j])
                sorted[k] = arr[i++];
            else
                sorted[k] = arr[j++];
            k++;
        }
 
        if (i > middle) {
            for (t = j; t <= n; t++, k++)
                sorted[k] = arr[t];
        } else {
            for (t = i; t <= middle; t++, k++)
                sorted[k] = arr[t];
        }
 
        for (t = m; t <= n; t++)
            arr[t] = sorted[t];
 
        System.out.println("\n 합병 정렬 >> ");
        SelectionSort.printArr(arr);
 
    }
}

핵심요약

1. 머지소트는 정복의 과정에서 정렬이 된다.

2. 머지소트는 정복의 과정에서 추가적인 배열을 필요로 한다.

3. 머지소트의 빅오는 nlogn이다. ->반으로 나누는것(logn) * 각 병합의 단계마다 n번 비교연산