알고리즘 with 파이썬 (3) - 병합정렬

리스트를 두 그룹으로 나누어 먼저 정렬하고, 두 그룹의 맨 앞부터 차례대로 병합하는 방식. 한 그룹의 자료가 모두 소진되면 남은 그룹의 정렬 상태 그대로 결과 리스트에 삽입하면 된다. 

이렇게 주어진 문제를 절반으로 나눈다음 각각 재귀호출로 풀어가는 방식을 '분할정복'이라고 함

시간 복잡도 O(n logn)으로 O(n²)인 선택/삽입정렬보다 빠르다. 

따라서 정렬해야할 자료의 개수가 많을 수록 병합정렬이 선택/삽입 정렬보다 좋은 성능을 보인다.

 

def merge_sort(a):
    n = len(a)
    #종료 조건
    if n<=1:
        return
    #그룹을 나누어 각각 병합정렬을 호출하는 과정
    mid = n//2
    g1 = a[:mid]
    g2 = a[mid:]

    merge_sort(g1) #재귀호출로 첫번째 그룹 정렬 - 이게 어떻게 정렬이 된다는거지?
    merge_sort(g2) #재귀호출로 두번쨰 그룹 정렬

    #두 그룹을 병합
    i1 =0
    i2 =0
    ia = 0

    while i1<len(g1) and i2< len(g2): #한 그룹이라도 length 만큼 다돌면 탈출
        if g1[i1]<g2[i2]:
            a[ia] = g1[i1]
            i1+=1
            ia+=1
        else:
            a[ia] = g2[i2]
            i2+=1
            ia+=1
    # 아직 남아있는 자료들을 결과에 추가
    while i1<len(g1):
        a[ia] = g1[i1]
        i1 += 1
        ia += 1
    while i2<len(g2):
        a[ia] = g2[i2]
        i2 += 1
        ia += 1

d = [2,6,23,67,22,4,66,75,35,18,92]
merge_sort(d) # 반환값은 없고 재정렬
print(d)

* 재귀함수로 두 그룹이 재정렬되는 원리를 잘 모르겠다. 순차적으로 공부하다보면 나온다고 해서 일단 PASS

** 두 그룹 병합 시 pop 과 len(g1)<0 조건을 이용할 수도 있다.