병합 정렬(merge sort)

📔 병합 정렬(merge sort) 이란

• 분할정복을 활용하여 구현하기 때문에 시간복잡도는 O(nlogn) 퀵정렬과 비슷

• 분할정복: 문제를 작은 2개의 문제로 분리하고 각각 해결한 후, 다시 모아 원래의 문제를 해결하는 방법.
  보통 재귀함수 호출을 이용하여 구한다.

• 퀵정렬과 다른 점이 있다면 퀵정렬의 경우 pivot값에 따라 편향되게 분할 될 수 있는 가능성이 있기 때문에 최악의 경우 O(n^2)의 시간복잡도를 가진다. 그러나 병합정렬의 경우 정확히 반씩 나눈다는 점에서 최악의 경우에도 O(nlogn)의 시간복잡도를 보장한다.
• 만약 8개의 숫자를 정렬한다고 하자. 8에서 4로 나누고, 4에서 2로 나누고, 2에서 1로 나눈다. 즉 3번 나눴다.
  그러므로 나누는 것은 3 = log8 이므로 logn이다.
  나눈 숫자의 대소를 비교하는 것: [1,3], [2,4] 를 정렬해보면
  1: 1 이 2보다 작으므로 [1]
  2: 2가 3보다 작으므로 [1,2]
  3: 3이 4보다 작으므로 [1,2,3]
  4: 마지막 남은 것 [1,2,3,4]
  4번 연산했다. N만큼 연산
  그래서 시간복잡도는 n*logn
• 비교 정렬 ( 다른 원소와의 비교 )
• 순차적인 비교를 통해 정렬을 진행하므로 LinkedList를 정렬할 때 사용하면 효율적이다.
  (LinkedList는 삽입 삭제 연산에서 유용하지만 접근 연산에서는 비효율적이므로)

 

📔 병합 정렬(merge sort) 예제

• 분할정복(divide and conquer)를 이용 - 재귀함수로 구현
• 먼저 리스트를 반씩 쪼갠다 . 더 이상 쪼갤 수 없을 때 까지 분할
• 다시 병합하면서 정렬해 나아간다.

분할 과정

• 합치는 방법은 가장 왼쪽 맨아래부터 시작한다.

📔 병합 정렬(merge sort) 구현

def merge_sort(div_numbers):
    if len(div_numbers) > 1:
        print(f'쪼개기: {div_numbers}')
        mid = len(div_numbers) // 2
        left_numbers = merge_sort(div_numbers[:mid])
        right_numbers = merge_sort(div_numbers[mid:])

        i, j, k = 0, 0, 0  # 왼쪽리스트 인덱스, 오른쪽 리스트 인덱스, 통합리스트인덱스
        while i < len(left_numbers) and j < len(right_numbers):
            if left_numbers[i] < right_numbers[j]:
                div_numbers[k] = left_numbers[i]
                i += 1
            else:
                div_numbers[k] = right_numbers[j]
                j += 1
            k += 1

        # 둘중 한쪽의 리스트를 다 썼음
        while i < len(left_numbers):
            div_numbers[k] = left_numbers[i]
            i += 1
            k += 1
        while j < len(right_numbers):
            div_numbers[k] = right_numbers[j]
            j += 1
            k += 1
    print(f'합치기: {div_numbers}')
    return div_numbers


numbers = [4, 2, 8, 6, 0, 5, 1, 7, 3, 9]
print(f'정렬 전: {numbers}')
print()
merge_sort(numbers)
print()
print(f'정렬 후: {numbers}')

 

📔 병합 정렬(merge sort) 특징

• 장점
  • 최악의 시간복잡도가 O(nlogn)이다.
  • 큰 데이터셋에서 매우 효율적이다.
  • 안정 정렬
• 단점
  
  • 추가적인 메모리가 필요하다. (정렬할 배열을 임시로 가지고 있어야 하므로)

📔 병합 정렬(merge sort) 참교자료