분할정복 알고리즘 - 합병 정렬

합병 정렬 (Merge Sort)

정의

- 분할 정복 알고리즘의 하나로 비교 기반의 정렬이다. 

- 정렬되지 않은 리스트를 절반으로 자른다. 크기가 1/2 감소

- 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

- 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

의사 코드 

mergeSort(arr, first,last){
    if(first < last){
      mid = (first + last) / 2;
    margeSort(arr, first, mid);
    margeSort(arr, mid, last);
    marge(arr, first, last);
  }
}

Java 구현

1. Input data array (numbers)와 helper array(helper) 2개를 만들어 합병을 할때 helper에 copy를 하여 옮겨 닮을 수 있도록 한다.

2. Mergesort 객체를 생성하여 sort를 호출하면 numbers와 같은 사이즈의 helper를 생성하고 mergesort 함수를 호출한다.

3. mergesort 함수에서는 시작 인덱스 low와 끝 인덱스 high가 같아질때까지 재귀 함수로 mergesort호출하고 더이상 분해가 안될 경우 merge함수를 호출하여 합병을 진행한다.

4. merge 함수에서는 해당 영역(log-high)을 helper 함수에 복사하고 복사된 값을 중간 값을 기준으로 left, right 인덱스를 이용해 차례대로 비교하고 작은 값을 numbers의 k에 위치 하게 한다. 

5. 비교가 끝난 후 왼쪽에 남은 것이 있다면 numbers에 차례로 추가한다. 

package de.vogella.algorithms.sort.mergesort;

public class Mergesort {
        private int[] numbers;
        private int[] helper;

        private int number;

        public void sort(int[] values) {
                this.numbers = values;
                number = values.length;
                this.helper = new int[number];
                mergesort(0, number - 1);
        }

        private void mergesort(int low, int high) {
                // check if low is smaller then high, if not then the array is sorted
                if (low < high) {
                        // Get the index of the element which is in the middle
                        int middle = low + (high - low) / 2;
                        // Sort the left side of the array
                        mergesort(low, middle);
                        // Sort the right side of the array
                        mergesort(middle + 1, high);
                        // Combine them both
                        merge(low, middle, high);
                }
        }

        private void merge(int low, int middle, int high) {

                // Copy both parts into the helper array
                for (int i = low; i <= high; i++) {
                        helper[i] = numbers[i];
                }

                int i = low;
                int j = middle + 1;
                int k = low;
                // Copy the smallest values from either the left or the right side back
                // to the original array
                while (i <= middle && j <= high) {
                        if (helper[i] <= helper[j]) {
                                numbers[k] = helper[i];
                                i++;
                        } else {
                                numbers[k] = helper[j];
                                j++;
                        }
                        k++;
                }
                // Copy the rest of the left side of the array into the target array
                while (i <= middle) {
                        numbers[k] = helper[i];
                        k++;
                        i++;
                }

        }
}

코드 출처: http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html

시간 복잡도

분할시 mid 인덱스 구하기, 2번의 재귀함수 호출 O(1)

합병시에는 각층에서 O(n)번의 비교를 진행 후 각 층의 수를 곱한 시간이 소요된다. 따라서 O(nlongn)의 시간 복잡도를 갖는다.

공간 복잡도

일반적 정렬 알고리즘은 입력 Array를 제외한 경우 O(1)의 공간 복잡도를 갖는다. (단순한 변수 할당, 인덱스 등)

하지만 merge sort의 경우 추가로 helper array가 필요하기 때문에 O(n)의 공간 복잡도를 갖는다.