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

분할 정복(Devide and Conquer) 기법과 재귀(Recursive) 알고리즘을 이용한 정렬 알고리즘입니다.

1. 배열의 중간을 기준으로 배열을 나눕니다.
2. 나누어진 배열들에 대해서 배열의 크기가 0또는 1이 될 때 까지 위의 과정을 반복합니다.
3. 나누어진 배열들을 정렬하며 병합합니다.

시간복잡도는 언제나 **O(nlogn)**입니다. 전반적인 반복의 수는 점점 절반으로 줄어들기 때문에 O(logn)의 시간이 필요하며,

각 단계에서 병합할 때 모든 값들을 비교해야 하므로 O(n)의 시간이 소모됩니다.

따라서 총 시간복잡도는 O(nlogn)입니다. 두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요합니다.

따라서 공간복잡도는 O(n) 입니다.

 

장점

• 안정적인 정렬입니다.
• 데이터 분포에 따른 시간 영향을 덜받습니다. 똑같은 크기로 나누어 정렬되기 때문에 시간은 동일합니다.
• 만약 배열을 **linked list(연결 리스트)**로 구현하면 인덱스만 변경되므로 데이터의 이동 및 복사를 하지
• 않아도 됩니다.
• 크기가 큰 배열을 정렬할 경우 연결리스트를 사용한다면, 합병정렬은 어떤 정렬보다도 효율적입니다.

단점

• 배열로 구성되어 있을 때, 임시 배열이 필요합니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    def merge(left, right):
        i, j = 0, 0
        sorted_list = []
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                sorted_list.append(left[i])
                i += 1
            else:
                sorted_list.append(right[j])
                j += 1

        while i < len(left):
            sorted_list.append(left[i])
            i += 1

        while j < len(right):
            sorted_list.append(right[j])
            j += 1
        return sorted_list

    return merge(merge_sort(left), merge_sort(right))