주요 함수
compare , move

A divide-and-conquer approach

크기가 커서 풀기 어려운 하나의 문제를 크기가 작아서 풀기 쉬운 여러 개의 문제로 바꾸어서 푸는 방법

Divide

n keys 를 두개의 n/2 keys로 나눈다.

Conquer

합병정렬을 사용하여 두 개의 배열을 정렬한다.

Combine

두 개의 정렬된 배열을 하나의 배열로 합친다.

코드

import math

mergelist = [5, 4, 7, 1, 3, 2, 8]


# Divide
def mergeSortFunc(A, p, r):
    if p < r:
        q = math.floor((p + r) / 2)
        mergeSortFunc(A, p, q)
        mergeSortFunc(A, q + 1, r)
        merge(A, p, q, r)


# Conquer

# Combine

def merge(A, p, q, r):

    L = []
    R = []
    # 들어왔을때 왼쪽 배열에 집어 넣는 수를 지정
    n1 = q-p
    n2 = r-(q+1)

    for i in range(n1+1):
        L.append(A[p+i])
    for j in range(n2+1):
        R.append(A[(q+1)+j])


    i=0
    j=0
    L.append(99999)
    R.append(99999)
    for z in range(p,r+1):
        if L[i] <= R[j]:
            A[z] = L[i]
            i = i+1
        else:
            A[z] = R[j]
            j = j+1
    # 들어오는 p,q는 왼쪽 배열의 시작점과 끝점
    # q+1,r은 오른쪽 배열의 시작점과 끝점

    # p~q까지의 아이템을 왼쪽 배열에 넣고
    # q+1~r 까지의 아이템을 오른쪽 배열에 넣는다.
    # 왼쪽 배열과 오른쪽 배열의 아이템들을 비교해서 A의 배열 값을 바꾸게 한다.


# main
if __name__ == "__main__":
    mergeSortFunc(mergelist, 0, len(mergelist)-1)
    print(mergelist)

# 배열을 분리한다. 1개의 배열만을 가지게하여
# 2개의 이미 정렬된 배열의 가장 왼쪽의 수들을 비교하여 작은 수를 또 다른 배열로 이동 시킨다.


# 배열의 p,r에 뭐를 줘야하나.

정리

합병정렬은 정렬된 배열 2개를 하나의 배열로 합치는 방법으로 두개의 배열의 가장 왼쪽 가장 작은 수들을 비교하여 모든 아이템들이 옮겨갈때 까지 반복하여 정렬 하는 방식입니다.