[python]합병 정렬

반갈죽..이 아니라 반갈정

합병정렬(Merge sort)이란?

---

합병정렬 또는 병합정렬이라고도 부르며, 먼저 절반으로 분할하고 합치면서 정렬하는 방법. 존 폰 노이만이 제안한 방법이며, 분할 정복 알고리즘의 하나이다.

1. 리스트 길이가 1이하이면 이미 정렬된 것으로 본고 그렇지 않은 경우에는
2. 분할단계(divide): 정렬되지 않은 리스트를 타노스 손가락 튕기듯이 절반을 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 마블 MCU로 생각하면 인피니트 워 단계
3. 정복단계(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합단계(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 마블 MCU로 치면 앤드 게임에 해당한다.

오른쪽과 같이 [6,5,3,1,8,7,2,4]라는 정렬되지 않은 배열이 있다고 가정하자. 분할 단계로 거치며 두 개씩 계속해서 나눈다.

이제 정복단계를 거치면서 6,5는 5,6으로 3,1은 1,3으로 각각 정렬되며 결합단계를 거치며 짝을 이루며 하나의 리스트로 합병한다. 이 과정을 완전히 하나된 합병이 이루어질 때까지 계속 반복한다.

이처럼 큰 문제를 작은 문제로 나눠서 푸는 방법을 알고리즘 설계 기법에서는 '분할 정복'이라고 부른다.

핵심은 두 부분으로 쪼개고 정렬하며 합친다

알고리즘의 특징

---

장점

• 안정적인 정렬 방법
• 다른 정렬들과 비교적 효율적
• 연결 리스트로 구성할 경우 레코드들의 데이터 이동이 적어진다.

단점

• 기존의 데이터를 담을 추가적인 배열 공간이 필요하다는 점에서 메모리 활용이 비효율적이라는 단점
• 레코드들의 크기가 큰 경우에는 이동 횟수가 많아져 시간적으로 낭비가 크다(그래서 연결 리스트로 레코드를 구성함)
• 다른 정렬들과 비교했을 때 복잡한 방법

시간복잡도

---

• 다른 정렬과 비교해서 비교적 복잡한 구현방식이지만 처리 속도가 빠른 효율적인 방법
• 비교 횟수와 이동 횟수만큼 시간복잡도가 늘어남
• 시간 복잡도 O(N*logN) 퀵정렬보다 빠른 건 아니지만 경우의 수가 늘어날 수록 어느 정도의 시간 복잡도를 보장한다.

코드

---

재귀 호출을 이용하기 때문에 끝나는 조건인 리스트가 1보다 작거나 같은 조건이 맨 먼저 들어와야 한다.

#합병 정렬
#리스트 a를 합병 정렬하는 코드

def merge_sort(a):
    n = len(a)
    #종료 조건:리스트 자료가 한 개 이하면 정렬할 필요가 없음
    if n <= 1:
        return
    #분할 단계 절반을 나누어서 두 그룹으로 나눔
    mid = n // 2
    a_front = a[:mid]
    a_back = a[mid:]
    merge_sort(a_front)
    merge_sort(a_back)
    i=0 #배열 앞에 부분 재귀호출 함수 제한하기
    j=0 #배열 뒤에 부분 재귀호출 함수 제한하기
    k=0 옮길 자리의 숫자#
    #결합단계
    while i < len(a_front) and j < len(a_back):
        if a_front[i] < a_back[j]: #이부분의 부등호를 바꾸면 내림차순으로 정렬이 바뀜
            a[k] = a_front[i]
            i += 1
            k += 1
        else:
            a[k] = a_back[j]
            j += 1
            k += 1
    #결합하고 남은 것들을 추가
    while i < len(a_front):
        a[k] = a_front[i]
        i += 1
        k +=1
    while j < len(a_back):
        a[k] = a_back[j]
        j += 1
        k += 1

a=[5,9,4,6,8,2,3,1,7,16,21]
merge_sort(a)
print(a)