병합 정렬 (Merge Sort)

O (N*logN)의 시간복잡도

분할 정복 방법을 채택한 알고리즘

정확히 반절씩 나눈다는 점에서 최악의 경우에도 O를 보장

 

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요

7 6 5 8 3 5 9 1

 

'일단 반으로 쪼개고 나중에 합쳐서 정렬'

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:] # 만약 오른쪽 배열이 먼저 mergerd_arr에 들어가면 왼쪽을 끝에 넣어주면 된다
    merged_arr += high_arr[h:] # 왼쪽 배열이 먼저 들어간경우 오른쪽 배열 추가
    return merged_arr