합병정렬

합병정렬이란?

n개의 숫자들을 n/2개씩 2개의 부분문제로 분할하고, 각각의 부분문제를 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)하는 과정입니다.

맨 위에 원소의 개수가 8인 배열이 정렬되어 있지 않습니다.
저 배열을 정렬하기 위한 방법을 반으로 나누어 정렬 후 합쳐서 정렬하는 것입니다.

1. 원소 8개 배열에서 반으로 나눕니다. 원소 4개의 배열이 됩니다.

2.원소 4개의 배열에서 반으로 나눕니다. 원소 2개의 배열이 됩니다.

3. 원소 2개의 배열에서 반으로 나눕니다. 원소 1개의 배열이 됩니다.

4. 원소 1개의 배열이 되었을 때 정복을 시작합니다. 분할한 2개의 배열(37, 10)중 작은 원소를 임시배열에 저장합니다.

5. 마찬가지로 원소 2개일 때 분할한 2개의 배열([10, 37], [22, 30]) 중 작은 원소를 임시배열에 저장합니다.

6. 마찬가지로 원소 4개일 때 분할한 4개의 배열 중 작은 원소를 임시배열에 저장합니다.

합병정렬 알고리즘 코드

def mergesort(arr):
    size = len(arr)
    if size <= 1:
        return arr

    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    merged = merge(left, right)

    return merged

def merge(arr1, arr2):
    merged = []
    while len(arr1) > 0 and len(arr2) > 0:
        if arr1[0] >= arr2[0]:
            merged.append(arr2.pop(0))
        else:
            merged.append(arr1.pop(0))

    if len(arr1) > 0:
        merged += arr1
    if len(arr2) > 0:
        merged += arr2

    return merged

mergesort 함수는 분할하는 함수입니다. 분할하다 종료조건으로 배열의 크기가 1일 때 종료를 합니다. 그리고 절반을 기준으로 분할합니다. left, right가 생기고 left, right를 합병합니다.

merge함수는 정복하는 함수입니다. merged는 임시배열이고 left, right배열 중 작은 값이 merged 배열에 들어갑니다.