[알고리즘] # 4_2 병합 정렬

** 병합 정렬(Merge sort)

• 재귀 용법과 분할 정복 알고리즘을 활용한 정렬 알고리즘
  • 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 분할
  • 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬
  • 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병

 

클릭시 출처 이동

 

 

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

 

 

** 구현

---

- mergesplit():  리스트의 개수가 1개일 때까지 분할하는 함수

 

def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2) 
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

 

- merge(): 2개의 리스트를 순회 및 비교하여, 1개의 정렬된 함수를 반환하는 함수

• 각 리스트의 맨앞 원소부터 각각 비교
• 둘 중 작은 값을 새로운 결과(merged) 리스트에 저장
• 다음 비교에서, 둘 중 작은 값을 가진 리스트는 그 값의 다음 원소부터 비교
• 만약, 하나의 리스트가 소진 될 경우, 나머지 리스트 통째로 결과 리스트에 그대로 저장하면 됨

 

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    # case1 - left/right 둘다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    # case2 - left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    # case3 - right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged

---

 

** 알고리즘 분석

- 알고리즘 분석이 쉽지 않으므로 참고 정도만

• 재귀 호출 과정을 이진 트리로 생각했을 때,
  • 트리의 층 i = 0 ~ (재귀 호출 수=logn)
  • i 층에서, 각 리스트의 길이 = n / 2^i
  • i 층에서, 리스트의 개수 = 2^i
  • 따라서 층별 호출시, 2^i * (n / 2^i) =  O(n)

 

• 재귀 호출은 총 logn번 실행되므로,  전체 시간 복잡도는 O(n) * O(logn) = O(n * logn)