[Python] 병합 정렬(Merge Sort)

 

 

정렬 알고리즘은 사실 실제로 구현해서 사용할 일은 없는 것 같다. 매일 잊어먹기 때문에 기록의 용도로 올린다. 병합 정렬(Merge Sort)의 시간복잡도는 최악의 경우부터 최선의 경우 모두 $O(n\ log\ n)$이고, 공간복잡도는 $O(n)$이다. 배열의 크기에 비례하는 공간이 필요하다. 

 

병합 정렬(Merge Sort)

 

 

병합 정렬은 배열을 재귀함수로 계속 분할하고 끝에서부터 병합하면서 정렬이 되는 구조다. 타고타고 병합이 완료되면서 정렬된다.

 

- 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

d = [1, 6, 8, 2, 9, 3, 7, 5, 4]

def merge_sort(d):
    if len(d) < 2:
        return d
    mid = len(d)//2
    l = merge_sort(d[:mid])
    r = merge_sort(d[mid:])
    i, j = 0, 0
    res = []
    while True:
        if i >= len(l) or j >= len(r):
            break
        if l[i] <= r[j]:
            res.append(l[i])
            i += 1
        else:
            res.append(r[j])
            j += 1
    if l[i:]:
        res.extend(l[i:])
    if r[j:]:
        res.extend(r[j:])
    return res

print(merge_sort(d))

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

d = [1, 6, 8, 2, 9, 3, 7, 5, 4]

def merge_sort(d):
    if len(d) < 2:
        return d
    mid = len(d)//2
    l = merge_sort(d[:mid])
    r = merge_sort(d[mid:])
    return merge(l, r)

def merge(l, r):
    if len(l) == 0 or len(r) == 0:
        return l or r
    i, j = 0, 0
    res = []
    while True:
        if i >= len(l) or j >= len(r):
            break
        if l[i] <= r[j]:
            res.append(l[i])
            i += 1
        else:
            res.append(r[j])
            j += 1
    if l[i:]:
        res.extend(l[i:])
    if r[j:]:
        res.extend(r[j:])
    return res

print(merge_sort(d))

 

 

 

[Python] 퀵 정렬(Quick Sort)

 

[Python] 힙 정렬(Heap Sort)