➕Merge Sort

orders

★ 원소를 개별적으로 나누고, 병합하는 두 과정이 수반되는 정렬 ★

(아래 과정 ②는 divide / ③은 merge)

(따라서 merge sort는 나누고 + 합치고 두 과정)

 

① 정렬할 데이터 준비 (오름차순 가정)

 

7 3 1 5 6 4 2

 

② 본격적인 merge sort를 하기에 앞서서 각각 원소가 1개씩만 있게끔 recursive하게 array를 절반으로 쪼갠다 (recursion 적용)

 

7 3 1 | 5 6 4 2 → 7 | 3 1 | 5 6 | 4 2 → 7 | 3 | 1 | 5 | 6 | 4 | 2

 

③-1) 두 개씩 쪼개는 루트의 역 방향으로 작은 원소를 앞에, 큰 원소를 뒤에 놓는다.

 

(1) 3 1 에서 3 | 1로 쪼갰으므로 1 3으로 정렬

 

(2) 5 6 에서 5 | 6으로 쪼갰으므로 5 6으로 정렬

 

(3) 4 2에서 4 | 2로 쪼갰으므로 2 4로 정렬

 

7 | 1 3 | 5 6 | 2 4

 

③-2) 계속해서 두 개씩 쪼갠 루트의 역 방향으로 정렬한다

 

(1) 7 3 1에서 7 | 3 1로 쪼갰으므로 7 | 1 3을 1 3 7로 정렬

 

(2) 5 6 4 2에서 5 6 | 4 2로 쪼갰으므로 5 6 | 2 4를 2 4 5 6으로 정렬

 

1 3 7 | 2 4 5 6

 

※ 이 때, 위 ③-2) 정렬은 구체적으로 아래와 같이 진행

 

➕두 개씩 쪼갠 루트의 역방향으로 병합(merge)하는 과정이므로, 무조건 두 배열만 존재. 이 때 심플하게 두 배열 각각의 제일 작은 원소끼리만 비교해서 더 작은 값을 먼저 선택해 정렬하는 방식으로 진행된다.

 

ex) 5 6 | 2 4를 2 4 5 6으로 정렬하는 과정

▶ 두 배열 (5 6과 2 4)각각의 최솟값 2와 5 비교. 2가 작으므로 2 먼저 선택해 앞에 정렬 (2)

▶ 남은 두 배열 (5 6과 4) 각각의 최솟값 4와 5 비교. 4가 작으므로 4 먼저 선택해 2 뒤에 정렬 (2 4)

▶ 한 배열이 모두 정렬되었으므로 나머지 배열 5 6 그대로 뒤에 붙이기 (2 4 5 6)

 

③-3) 역시 계속해서 두 개씩 쪼갠 루트의 역 방향으로 정렬한다.

 

(1) 7 3 1 | 5 6 4 2 에서 7 3 1 | 5 6 4 2로 쪼갰으므로 1 3 7 | 5 2 4 6을 1 2 3 4 5 6 7로 정렬(완료!😄)

 

➕두 배열의 병합 과정은 각 배열의 첫번째 원소에 포인터를 두고 포인터가 업데이트됨으로써 진행된다. 포인터를 이용한 병합 정렬은 아래 예로 그림을 통해 알아보자.

 

★ 두 배열 각각의 맨 앞에 포인터를 둔다.

★ 맨 앞의 포인터가 가리키는 두 원소(1,2) 중 최솟값 answer 배열에 먼저 넣고, answer에 넣은 원소가 가리키는 포인터는 오른쪽으로 이동

★ 그 다음 두 포인터가 가리키는 두 원소(3,2) 중 최솟값을 answer 배열에 넣고, answer에 넣은 원소가 가리키는 포인터를 오른쪽으로 이동

★ 이와 같이 계속해서 진행

 

④ 1 2 3 4 5 6 7 완성!

about Merge Sort

★ 두 배열 씩 쪼개는 과정에서 O(logN) / 쪼개진 두 배열을 병합하는 과정에서 O(N) (위 그림에서와 같이 두 포인터 각각이 traversing하는 범위가 정확히 각 원소당 1번 - 즉 O(N)이 된다). 따라서 쪼개진 두 배열마다 각각 병합을 나중에 진행하므로 두 time complexity를 곱한 O(NlogN)이 최종 merge sort의 time complexity

 

★ merge sort의 큰 장점은 무조건 모든 array가 two halves로 split되고, split된 two halves subarrays는 무조건 merging하기 때문에 worst, average, best case 모든 시나리오에서 time complexity는 O(NlogN). 따라서 매우 큰 데이터셋에서도 적용 가능한 정렬 알고리즘. / space complexity는 O(N) - answer array로 정렬하기 위한 N length의 array 필요(위 그림 노란색 answer array)

 

★ a recursive algorithm that continuously splits the array in half until it cannot be further divided i.e., the array has only one element left (an array with one element is always sorted). Then the sorted subarrays are merged into one sorted array.

 

★ stable한 정렬 알고리즘: original array에서 동일한 값을 가지는 순서는 해당 순서 그대로 유지된 채로 정렬된다.

 

★ space complexity가 O(N)이므로 추가 메모리가 필요한 단점 존재

 

★ small dataset에서도 O(NlogN)이기 때문에 insertion sort의 best-case scenario O(N)에 비해서는 비효율적이라고 할 수 있다.

Merge Sort Code

★ pesudo-code (array A를 ascending order로 sorting한다고 가정. ascending order로 sorting할 배열의 index는 p ~ r 가정)

 

▶ Merge Sort는 두 개의 subarray로 나누는 merge_sort() 함수 & 합치는 merge() 함수로 나눌 수 있다. (아래 그림 merge_sort() 함수로 쭉 내려갔다가 맨 아래에서 merge()로 계속 올라옴: 과정을 머릿속으로 기억하자!)

① merge_sort()

: 두 subarray로 나누기

▶  index p ~ r에 해당하는 배열 A의 subarray를 나눈다. 배열 A에 들어간 원소의 개수가 2개 이상일 경우만 나뉜다.

(1) p와 r의 중간 index를 q라고 지정.

(배열 A의 원소 개수가 홀수일 경우 left subarray의 개수가 1개 더 많다)

(2) p ~ q에 해당하는 왼쪽 subarray / q+1 ~ r에 해당하는 오른쪽 subarray 준비.

(3) 두 subarray 각각 재귀적으로 merge_sort() 함수 실행

(4) 배열 A에 들어간 원소가 1개일 때까지 나뉜다.

 

▶  python

def merge_sort(A,p,r): #sort in ascending order (index p ~ r in array A)
    if p<r: #check if the subarray's length is bigger than 1
        q = (p+r)//2
        merge_sort(A,p,q) #sorting left-side array
        merge_sort(A,q+1,r) #sorting right-side array
        merge(A,p,q,r) # merge

 

② merge()

: 나눠진 두 subarray를 오름차순 배열에 맞게 합치기

▶ index 기준 왼쪽 subarray(p ~ q)와 오른쪽 subarray(q+1 ~ r) 오름차순 배열에 맞게 합치기

(1) 두 subarray의 각각 맨 왼쪽 끝 시작점을 i와 j라고 하기 / 빈 배열 tmp [] 만들어서 update된 결과를 한 개씩 넣기

(2) 첫 while문 돌리기: i가 q가 될 때까지 & j가 r이 될 때까지 돌리기

: A[j]가 A[i]보다 크거나 같다면 A[i]를 tmp에 넣기. 그 반대라면 A[j]를 tmp에 넣기

(3) 왼쪽 subarray 또는 오른쪽 subarray 내용이 일부 남았다면(한쪽 subarray를 끝까지 다 돌았다면 남은 subarray가 돌 원소 일부가 남았다) 그 다음 while문 돌려서 tmp에 넣기

(4) 최종 tmp list를 A에 재할당(이 때, 실제 A 내용이 update된다)

 

▶ python

def merge(A,p,q,r): #merge A[p,...,q] & A[q+1,....,r] and sort A[p,...r]
    #A[p,...q] & A[q+1,...r] each sorted already
    i,j=p,q+1
    tmp=[]
    while (i<=q and j<=r):
        if A[i]<=A[j]:
            tmp.append(A[i])
            i+=1 #move pointer
        else:
            tmp.append(A[j])
            j+=1
    while (i<=q): #if left-side array has some remaining elements...
        tmp.append(A[i])
        i+=1
    while (j<=r): #if right-side array has some remaining elements...
        tmp.append(A[j])
        j+=1
    i,t=p,0
    while (i<=r):
        A[i] = tmp[t]
        i+=1
        t+=1

examples

★ <백준 24060 S3 알고리즘 수업 - 병합 정렬 1>

Q. merge() 합치는 과정에서 기존 subarray A에서 새로운 list tmp로 update되는 K번째 수 구하기

 

★ <백준 24061 S4 알고리즘 수업 - 병합 정렬 2>

Q. 위 24060에서 update된 K번 횟수 이후 바뀐 전체 array 배열 출력하기

---

코드없는 프로그래밍 YT

geeksforgeeks