3.1. Sorting - 3.1.6 Merge Sort

CS - 3. Common Algorithms - 3.1. Sorting - 3.1.6 Merge Sort

 

💡Merge sort is a divide and conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

 

병합 정렬은 분할 및 정복 알고리즘입니다. 이 함수는 입력 배열을 두 개의 반으로 나누고, 두 개의 반에 대해 스스로를 호출한 다음 정렬된 두 개의 반을 병합합니다. merge() 함수는 두 개의 반쪽을 병합하는 데 사용됩니다. merge(arr, l, m, r)는 배열[l..m]과 배열[m+1..r]이 정렬되어 있다고 가정하고 정렬된 두 개의 하위 배열을 하나로 병합하는 핵심 프로세스입니다.

 

정렬 Sorting 의 마지막 Merge sort 병합 정렬입니다.

 

병합 정렬은 퀵정렬과 마찬가지로 분할정복 방식의 정렬 알고리즘입니다.

주어진 문제를 작은 부분으로 나눈 뒤 각각을 해결하고, 이를 다시 합쳐서 전체 문제를 해결하는 방식을 사용합니다.

 

병합 정렬의 동작 과정은 이렇습니다.

 

1. 주어진 배열을 절반씩 나눕니다.

이를 재귀적으로 반복하여 배열의 길이가 1이 될 때 까지 나눕니다.

길이가 1인 배열은 자연스럽게 정렬된 상태로 간주합니다.

 

2. 이렇게 나눈 배열들을 다시 합치면서 정렬합니다.

이를 병합(Merge)라고 하며, 이 과정에서 실제 정렬이 이루어 집니다.

이를 재귀적으로 반복하여 전체 배열이 정렬될 떄까지 수행합니다.

 

 

In Python

 

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

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

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

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

 

 

병합 정렬은 항상 O(n log n)의 시간 복잡도를 가집니다.

이는 각 단계에서 n개의 원소를 다루고, 전체 단계의 수가 log n이기 떄문입니다.

 

병합 정렬은 안정적인 정렬 알고리즘이므로 동일한 값에 대해 원래의 순서가 유지되는 것이 중요한 상황에서 유용합니다.

또한 데이터의 크기가 크거나, 외부 정렬이 필요한 경우에도 사용됩니다. 그러나 병합 정렬은 추가적인 메모리 공간을 필요로 하는데, 이는 병합 과정에서 새로운 배열을 생성하기 때문입니다. 

따라서 메모리가 제한적인 상황에서는 사용하기 어려울 수 있습니다. 

 

 

 

위에서 

'병합 정렬은 안정적인 정렬 알고리즘이므로 동일한 값에 대해 원래의 순서가 유지되는 것이 중요한 상황에서 유용합니다.'

라는 말을 했습니다.

 

간단한 예시를 들자면

items = [(2, 'B'), (1, 'B'), (2, 'A'), (1, 'A')]

이러한 메인키(숫자int)와 보조키(문자str)로 구성되어있는 튜플의 리스트가 있습니다.

 

 병합정렬은 안정적인 정렬 알고리즘 이므로 원래의 순서가 유지되어야 합니다. 따라서,

뭐여??? [(1, 'B'), (1, 'A'), (2, 'B'), (2, 'A')] 이게 나와야하는데 싹 정리되서 나와버렸다.

(좀더 공부한뒤 차후 추가)

 

 

 

 

병합 정렬에서의 '안정성'이란, 동일한 값을 가진 원소들 사이의 상대적 순서가 정렬 후에도 유지된다는 것 입니다.

 

 

 

 

Appendix

LinkedList 에서의 Merge Sorting
병합 정렬은 순차적인 비교를 통해 정렬하기 때문에, 순차 접근에 용이한 LinkedList 의 정렬이 필요할 때 매우 효율적으로 동작하게 된다. 퀵 소트는 순차 접근이 아닌 임의 접근을 통해 정렬을 하기 때문에 오버헤드가 발생하여 성능이 좋지 않다.

(https://velog.io/@haero_kim/%EC%95%88%EC%A0%95%EC%A0%81-%EA%B7%B8-%EC%9E%90%EC%B2%B4-Merge-Sort)

 

 

 

 

https://www.geeksforgeeks.org/merge-sort/

Merge Sort - Data Structure and Algorithms Tutorials - GeeksforGeeks