Advanced Algorithm - 병합 정렬 (Merge Sort)

1. 병합 정렬이란? 

- 분할 정복 알고리즘을 기반한 정렬이다. 

- 재귀용법을 사용한다. 

 

a) 병합 정렬의 동작 방식

1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 

 

 

---

2. 어떻게 구현할까? 

 

필요한 기능

1. 단위 데이터까지 나누는 기능

* 단위 데이터: 더 이상 분리될 수 없는 데이터

 

2. 나눠진 데이터를 정렬하면서 합치는 기능 

 

3. 재귀 용법을 활용하여 1번과 2번 기능을 구현

---

3. 코드 구현

1) 리스트를 분리하는 기능 

def split(data):
    medium = int(len(data) / 2) #리스트의 중간위치 
    left = data[:medium]
    right = data[medium:]
    return split(left), split(right)

 

 

2) 분리된 리스트를 정렬 및 병합하는 기능 

def merge(left, right):
    storage = list() #합칠 때 사용할 별도의 리스트 공간
    left_index, right_index = 0,0
    
    # case1: left와 right가 모두 남아있을 때
    while len(left) > left_index and len(right) > right_index:
        if left[left_index] > right[right_index]:
            storage.append(right[right_index])
            right_index += 1
        else: 
            storage.append(left[left_index])
            left_index += 1
        
    # case2: left만 남아있을 때
    while len(left) > left_index:
        storage.append(left[left_index])
        left_index += 1
        
    # case3: right만 남아있을 때
    while len(right) > right_index:
        storage.append(right[right_index])
        right_index += 1
        
    return storage

 

 

3) 위의 두 가지 기능을 재귀함수로 구현 

def merge_split(data):
    if len(data) <= 1:
        return data
    else:
        medium = int(len(data) / 2) #리스트의 중간위치 
        left = merge_split(data[:medium])
        right = merge_split(data[medium:])
        return merge(left, right)

 

 

4) 최종 코드

def merge(left, right):
    storage = list() #합칠 때 사용할 별도의 리스트 공간
    left_index, right_index = 0,0
    
    # case1: left/right가 아직 남아있을 때
    while len(left) > left_index and len(right) > right_index:
        if left[left_index] > right[right_index]:
            storage.append(right[right_index])
            right_index += 1
        else: 
            storage.append(left[left_index])
            left_index += 1
        
    # case2: left만 남아있을 때
    while len(left) > left_index:
        storage.append(left[left_index])
        left_index += 1
        
    # case3: right만 남아있을 때
    while len(right) > right_index:
        storage.append(right[right_index])
        right_index += 1
        
    return storage




def merge_split(data):
    if len(data) <= 1:
        return data
    else:
        medium = int(len(data) / 2) #리스트의 중간위치 
        left = merge_split(data[:medium])
        right = merge_split(data[medium:])
        return merge(left, right)
        

 

 

[테스트 및 결과]

---

4. 병합정렬의 시간복잡도

 

 

[설명]