병합정렬

쉽게 설명한 선택 정렬 알고리즘

a =[6,8,3,9,10,1,2,4,7,5]
n = len(a) = 10
if n <= 1: #n이 1보다 작거나 같을 때 까지
return a
mid = n//2 = 5

1단계: G1 재귀함수

g1 = merge_sort(a[:mid]) = merge_sort([6,8,3,9,10])
   =1) g1 = [6,8], 2) g2 = [3,9,10]
    1-1) g1 = [6] , g2 = [8] 
    2-1) g1 = [3], g2 = [9,10]
    2-2) g1 = [9], g2 = [10]
    = [3,6,8,9,10]

g1과 g2가 모두 빈리스트가 아니기 때문에

2-2) g1 과 g2 함수 실행하면 [9,10]
g1 = [9], g2 = [10] -> [9,10]
2-1) g1 과 g2 함수 실행하면 [3,9,10]
g1 = [3] g2 = [9,10] -> [3,9,10]
1-1) g1 과 g2 함수 실행하면 [6,8]
g1 = [6] g2 = [8] -> [6,8]
1)+2) g1 과 g2 함수 실행하면 [3,6,8,9,10]
g1 = [6,8] g2 = [3,9,10] -> [3,6,8,9,10]

2단계: G2 재귀함수

g2 = merge_sort(a[mid:]) = merge_sort([1,2,4,7,5])
1) g1 = [1,2], 2) g2 = [4,7,5]
1-1) g1 = [1], g2 = [2] 
2-1) g1 = [4], g2 = [7,5]
2-2) g1 = [7] g = [5]
= [1,2,4,5,7]

g1과 g2가 모두 빈리스트가 아니기 때문에

2-2) g1 과 g2 함수 실행하면 [5,7]
g1 = [7], g2 = [5] -> [5,7]
2-1) g1 과 g2 함수 실행하면 [4,5,7]
g1 = [4] g2 = [5,7] -> [4,5,7]
1-1) g1 과 g2 함수 실행하면 [1,2]
g1 = [1] g2 = [2] -> [1,2]
1)+2) g1 과 g2 함수 실행하면 [1,2,4,5,7]
g1 = [1,2] g2 = [4,5,7] -> [1,2,4,5,7]

3단계: 1단계 G1과 2단계 G2의 while문 수행 후 최종 result

g1 = [3,6,8,9,10]
g2 = [1,2,4,5,7]
result = [1,2,3,4,5,6,7,8,9,10]

일반적인 병합 정렬 알고리즘

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):
        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

a =[6,8,3,9,10,1,2,4,7,5]
n이 1이 되는 과정, n이 1이 되고 난 후 다시 역순해서 while문이 계산되는 과정에 유의하며 보세요!

n = 10 , mid = 5
1) g1 = a[:mid] = [6,8,3,9,10]
2) g2 = a[mid:] = [1,2,4,7,5]

1-1) n = 5, mid = 2
1-1-1) g1 = a[:mid] = [6,8]
1-1-2) g2 = a[mid:] = [3,9,10]

1-1-1) n = 2, mid = 1
g1 = a[:mid] = [6]
g2 = a[mid:] = [8]

1-1-1) n = 1, n이 1이므로 if문 종료 및 while문 실행
a = [6,8]

1-1-2-1) n = 3, mid = 1
g1 = [3]
g2 = [9,10] = 1-1-2-3 실행 결과 [9,10]

1-1-2-2) n = 2, mid = 1
g1 = [9]
g2 = [10]

1-1-2-3) n = 1, n이 1이므로 if문 종료 및 while문 실행
g1 = [9]
g2 = [10]
a = [9,10]

1-1-2-1) while문 실행
g1 = [3]
g2 = [9,10]
a = [3,9,10]

1-1-1)+1-1-2-1) while문 실행
g1 = [6,8]
g2 = [3,9,10]
a = [3,6,8,9,10]

같은 방식으로 [1,2,4,7,5]를 진행하면
[1,2,4,5,7] 이 나옴

g1 = [3,6,8,9,10]
g2 = [1,2,4,5,7]
while문 실행하면

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