병합정렬 예시

• 주어진 배열: [38, 27, 43, 3, 9, 82, 10]
• 분할 과정: [38, 27, 43, 3]과 [9, 82, 10]로 나뉩니다.
• 더 분할: [38, 27], [43, 3], [9, 82], [10]
• 최소 단위까지 분할: [38], [27], [43], [3], [9], [82], [10]
• 정복 및 결합: 각 부분을 정렬하고 병합하면서 최종적으로 전체 배열이 정렬됩니다.

최소 단위 까지 분할이 되었다면 

병합하면서 대소를 교하면서 buff 배열에 넣고 남은배열을 넣는다 .

• [27,38]  [3,43]    [9,82] [10]
• [3,27,38,43]  [9,10,82]
• [3,9,........,82]

 

보던책이 너무 c언어 스럽게? ..?  풀이를해서 파이썬스럽게 풀으신분을 참고했다.

https://codingsmu.tistory.com/133

import sys


def merge_sort(arr: list):
    # 리스트의 크기가 1이하로 될때까지 분할함
    if len(arr) <= 1:
        return arr

    # 리스트의 크기가 1이 아니라면 2분할
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # 2분할한 리스트를 merge sort 진행
    left_ = merge_sort(left)
    right_ = merge_sort(right)
    return merge(left_, right_)
def merge(left, right):
    i, j = 0, 0
    sorted_list = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1
    # 남는 배열 처리하기
    while i < len(left):
        sorted_list.append(left[i])
        i += 1
    while j < len(right):
        sorted_list.append(right[j])
        j += 1

    return sorted_list

n = int(input())
arr =[int(sys.stdin.readline()) for _ in range(n)]
arr=merge_sort(arr)
[print(x) for x in arr]

---

 

파이썬의 내장함수를 이용하면 더 쉽다는 내용도 추가 합시다 ..!