[알고리즘] 병합 정렬 merge sort

병합 정렬 (합병 정렬) merge sort

• 동적 프로그래밍과 달리 memorization 방법은 쓰지 않고 재귀용법을 씀
• 분할정복 알고리즘을 사용한 정렬 알고리즘 중 하나임
  • 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 나눈다. ( 리스트를 자르는 함수)
  • 각 부분 리스트를 재귀적 합병 정렬을 이용하여 정렬한다.
  • 두 부분의 리스트를 다시 하나의 정렬된 리스트로 합병한다.

https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

---

이해

---

코드

• split, merge 함수가 필요함

def merge(left, right):
    merged = list()
    lp, rp = 0, 0 #index 번호

    
    #case1: left, right에 값이 있을 때
    while len(left) > lp and len(right) > rp :
        if left[lp] > right[rp]:
            merged.append(right[rp])
            rp += 1
        else:
            merged.append(left[lp])
            lp += 1
    
    #case2: left만 남음
    while len(left) > lp:
        merged.append(left[lp])
        lp += 1
        
    #case3 : right만 남음
    while len(right) >rp:
        merged.append(right[rp])
        rp += 1
            
    return merged
    
    ---------------------------------------------------------------------------------
    
   def merge_sort(data):
    if len(data)<=1:
        return data
    medium = int(len(data)/2)
    left = merge_sort(data[:medium])
    right = merge_sort(data[medium:])
    return merge(left, right

import random

data_list = random.sample(range(100), 10)
print(data_list)

merge_sort(data_list)

[31, 34, 66, 69, 91] [0, 4, 48, 82, 86]
[0, 4, 31, 34, 48, 66, 69, 82, 86, 91]

---

시간복잡도

list 나누기

단계에 있는 노드 list의 길이는 \( \frac {n} {2^{n}} \) 이 되고 노드는 \( 2^{n} \) 개가 된다.

이때 시간 복잡도는  \( 2^{n} \) * \( \frac {n} {2^{n}} \) 로 \( O(n)  \) 이 된다

 

list 병합

단계는 \( log_{2}n \)개 만들어진다 \( O(log(n) \)

 

merge sort의 시간 복잡도는 \( O(n log n) \) 이다