[알고리즘] 병합 정렬

오늘은 병합 정렬 알고리즘에 대해 공부하였다.
병합 정렬은 배열을 작게 분해하여 이를 병합하면서 순서를 맞춰가며 정렬된 알고리즘을 만드는 정렬 방법이다.

병합을 하기 위해서 먼저 주어진 숫자 리스트를 작은 단위로 쪼개 주어야 한다.

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

    return merge(left, right)

가장 작은 단위(길이가 1인 리스트)로 쪼개진 리스트를 비교하여 병합해 주면서 순서를 맞춰가게 된다.

def merge(left, right):
    result = list()
    left_point, right_point = 0, 0
    while len(left) > left_point and len(right) > right_point: 
        if left[left_point] < right[right_point]:
            result.append(left[left_point])
            left_point += 1
        else:
            result.append(right[right_point])
            right_point += 1

    while len(left) > left_point:
         result.append(left[left_point])
         left_point += 1

    while len(right) > right_point:
        result.append(right[right_point])
        right_point += 1

    return result

전체 코드는 아래와 같다.

import random
def split(data):
    if len(data) <= 1:
        return data
    
    medium = int(len(data)/2)
    left = split(data[:medium])
    right = split(data[medium:])

    return merge(left, right)

def merge(left, right):
    result = list()
    left_point, right_point = 0, 0
    while len(left) > left_point and len(right) > right_point: 
        if left[left_point] < right[right_point]:
            result.append(left[left_point])
            left_point += 1
        else:
            result.append(right[right_point])
            right_point += 1

    while len(left) > left_point:
         result.append(left[left_point])
         left_point += 1

    while len(right) > right_point:
        result.append(right[right_point])
        right_point += 1

    return result


data = random.sample(range(100), 5)
print(split(data))