분할정복 병합정렬 (파이썬)

병합 정렬

• 병합 정렬은 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식
• 분할 정복 알고리즘을 활용
• 시간복잡도 O(nlogn)

 

분할 작업

 

 

병합 작업

 

파이썬 코드

from collections import deque; import sys; sys.stdin = open('input_분할정복_백트래킹.txt', 'r')


def merge_sort(lst):
    global cnt
    if len(lst) == 1:
        return lst
    # 왼쪽과 오른쪽을 나눔
    mid = len(lst)//2
    left = lst[:mid]
    right = lst[mid:]
    # 왼쪽 부분과 오른쪽 부분을 재귀
    l = merge_sort(left)
    r = merge_sort(right)

    # 병합 과정 rst는 최종 return할 리스트임
    rst = []
   
    # pop(0)을 하면 실행시간이 너무 길어져서 인덱스를 사용
    i = 0
    j = 0
    len_l = len(l)
    len_r = len(r)

    # 두 인덱스가 모두 범위를 벗어나면 종료
    while i < len_l or j < len_r:
        # i 가 len(l)과 같아진다면 왼쪽 리스트의 비교해줄 값이 더이상 없다는 뜻
        # 즉, 오늘쪽의 인덱스를 순서대로 넣어주면 됨
        if i == len(l):
            rst.append(r[j])
            j += 1
            continue
        if j == len(r):
            rst.append(l[i])
            i += 1
            continue
        # 왼쪽의 i인덱스가 오늘쪽의 j인덱스보다 작다면 왼쪽의 i인덱스를 append해주고 i += 1
        if l[i] <= r[j]:
            rst.append(l[i])
            i += 1
        else:
            rst.append(r[j])
            j += 1

    return rst

for tc in range(int(input())):
    N = int(input())
    nums = list(map(int, input().split()))

    print(merge_sort(nums))