[알고리즘] 병합 정렬 Merge Sort

병합 정렬이란

• 분할 정복 알고리즘의 기법을 사용한다.
• 합병 정렬이라고도 불린다.
• 재귀 용법을 이용해서 리스트를 잘게 자른다. 그 안에서 다시 또 자른다. 그 뒤에 두 개씩 묶어서 정렬한다.
• 분리하는 단계, 합병하는 단계로 크게 나뉜다.

 

병합 정렬 실행 모습

 

 

알고리즘 구현하기

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)

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

import random

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

data_list = [21, 75, 53, 35, 38, 23, 93, 10, 97, 13]

Out[6]: [10, 13, 21, 23, 35, 38, 53, 75, 93, 97]

 

GitHub - DAWUNHAN/Algorithms-and-DataStructure: Algorithms and DataStructure with Python