Algorithm - Merge Sort

Merge Sort

Quick Sort와 유사한 알고리즘으로 배열을 분할 정복을 통해 구현되는 알고리즘

분할 정복
배열을 2개로 분리하고 각각을 해결한 다음 결과를 모아서 원래대로 배열을 모으는 방법

 

구현

• 리스트의 길이가 1 이하이면 이미 정렬된 것
• 분할 : 정렬되지 않은 리스트를 절반으로 잘라 두 리스트로 나눔
• 정복 : 각 부분 리스트를 재귀적으로 병합해 정렬
• 결합 : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 임시배열에 정렬 결과가 저장되어 추가 메모리 사용
• 복사 : 임시 배열에 저장된 결과를 원래 배열에 복사

# mergeSort : 분할
def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

# merge : 정렬 및 합병
def merge(left, right):
    answer = []
    while len(left) or len(right):
        # 1. left, right 둘 다 남았을 때
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                answer.append(left[0])
                left = left[1:]
            else:
                answer.append(right[0])
                right = right[1:]
        # 2. left만 남았을 때
        elif len(left) > 0:
            answer.append(left[0])
            left = left[1:]
        # 3. right만 남았을 때
        elif len(right) > 0:
            answer.append(right[0])
            right = right[1:]
    return answer

 

공간 복잡도

 분할된 리스트를 정렬하고 결합하는 과정에서 임시배열에 결과를 저장하기 위해 추가적으로 메모리를 사용하여 O(n)

 

시간 복잡도

분할 시에 반복의 수가 절반으로 줄어들기 때문에 O(logn)의 시간이 필요하고,

정복하고 결합하는 과정에서 모든 값을 비교해야하므로 O(n)의 시간이 소요되므로 O(nlogn)

n개의 데이터를 반씩 나누면 depth는 log2n개가 되고,
그 과정을 자세히 살펴보면 n개를 나누면 n/2가 2개 생기고, 2 * (n/2)를 반으로 나누면 n/4가 4개가 생긴다. 그래서 결국 각각의 depth를 정렬하고 결합하는 과정은 n = 2 * (n/2) = 4 * (n/4) = ... = n/2 * (2)이므로 n의 시간이 소요된다. 그래서 n * log2n의 시간복잡도로 계산된다.

 

장점

• 데이터에 상관없이 정렬되는 시간은 O(nlog2n)으로 동일
• 연결리스트로 구성하면 링크 index만 변경되므로 in-place sorting(제자리 정렬)로 구현할 수 있음
• 연결리스트를 사용하여 크기가 큰 레코드를 정렬할 경우, 가장 효율적인 정렬 방법

 

단점

• 배열로 Merge Sort를 구현하면 임시 메모리 공간이 필요함

 

Merge Sort 최적화

slice를 사용하게 되면 배열의 복제가 발생해 추가 메모리 공간이 필요하다는 것을 개선하기 위해, 새로운 배열을 매번 생성하지 않고 인덱스로 접근하여 in-place sorting을 구현하게 되면 메모리 사용량을 줄일 수 있음

def mergeSort(arr, left, right):
    if left < right:
        mid = (left + right) // 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, right)
        return merge(arr, left, mid, right)


def merge(arr, left, mid, right):
    tmp = mid + 1
    # [1, 4] 와 같이 이미 정렬된 상태일 때는 그대로 return
    if arr[mid] <= arr[tmp]:
        return

    # left는 mid와 같거나 작을 때까지, right는 mid + 1과 같거나 작을 때까지 반복
    while left <= mid and tmp <= right:
        # 예를 들어, [1, 4] [3, 6]에서 1과 3을 비교해서 왼쪽 값이 더 작다면 left 인덱스 증가
        if arr[left] <= arr[tmp]:
            left += 1
        # 예를 들어, [3, 4], [1, 2]과 같은 경우 3과 1을 비교했을 때, 왼쪽값이 더 클 경우
        else:
            val, idx = arr[tmp], tmp
            # 삽입 정렬?
            while idx != left:
                arr[idx] = arr[idx - 1]
                idx -= 1
            arr[left] = val
            left += 1
            mid += 1
            tmp += 1
    return arr
    
arr = [1, 4, 6, 22, 41, 2, 7]
print(mergeSort(arr, 0, len(arr) - 1))