병합정렬 (Merge Sort) - python

def merge(arr, start, mid, end):
    temp = [None] * len(arr)

    i = start
    j = mid + 1
    k = start

    while i <= mid and j <= end:
        if(arr[i] <= arr[j]):
            temp[k] = arr[i]
            i += 1
            k += 1
        else :
            temp[k] = arr[j]
            j += 1
            k += 1
    
    while i <= mid:
        temp[k] = arr[i]
        k += 1
        i += 1

    while j <= end:
        temp[k] = arr[j]
        k += 1
        j += 1


    for i in range(start, end + 1):
        arr[i] = temp[i]

def mergeSort(arr, start, end):
    if start < end:
        mid = (start + end) // 2

        mergeSort(arr, start, mid)
        mergeSort(arr, mid + 1, end)
        merge(arr, start, mid, end)

arr = [31, 53, 75, 42, 15, 64, 31] #정렬할 배열
print("[정렬되지 않은 배열]")
print(arr)
print()

start = 0
end = len(arr) - 1
mergeSort(arr, start, end)

print("[정렬 완료된 배열]")
print(arr)

[정렬되지 않은 배열]
[31, 53, 75, 42, 15, 64, 31]

[정렬 완료된 배열]
[15, 31, 31, 42, 53, 64, 75]

1. 배열을 반으로 나눈다. 재귀 때문에 계속 나뉜다.

2. 할 수 있는 끝까지 나눈다.

3. 전반부와 후반부의 첫 원소를 비교한 뒤 합친다.

4. 이걸 재귀하여 계속 반복하며 비교 및 병합 한다.

정렬 완료.