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

병합 정렬

• 비교 기반 정렬 알고리즘
• 병렬을 앞 부분과 뒷 부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘
• 안정한 정렬(Stable sort)
• 분할 정복 알고리즘
• 1945년 폰 노이만이 개발

과정

1. 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에 다음 과정을 거친다.
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다.

• 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 합병 정렬은 다음의 단계들로 이루어진다.
  • 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  • 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
  • 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 병합한다.
• 병합 정렬의 과정
  • 추가적인 리스트가 필요하다.
  • 각 부분 배열을 정렬할 때도 병합 정렬을 순환적으로 호출하여 적용한다.
  • 병합 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 병합(merge)하는 단계이다.

 

병합 정렬의 장단점

장점

• 안정적인 정렬 방법
  • 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다.($O(n \log_{2}n)$으로 동일)
• 만약, 레코드를 연결 리스트(Linked list)로 구성하면 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
  • 제자리 정렬(in-place sorting)으로 구현할 수 있다.
• 따라서, 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 병합 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적이게 된다.

단점

• 만약 레코드를 배열(Array)로 구성하면 임시 배열이 필요해진다.
  • 제자리 정렬(in-place sorting)이 아니다.
• 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초례한다.

Python Code

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

 

Java Code

public class MergeSorter {
    public static int[] sort(int[] arr) {
        if (arr.length < 2) return arr;

        int mid = arr.length / 2;
        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;
    }
}