병합정렬 (python으로 구현하기)

---

 

Merge Sort

병합정렬?

정렬되어 있지 않은 배열을 1/2씩 재귀적으로 나누어 준 다음에, 다시 요소 끼리 차례로 합칠때 정렬을 하면서 합치는 과정을 말한다. 그런식으로 마지막에 전부 합쳐질 경우 정렬된 상태가 된다.

 

예를들어 2개의 정렬된 배열이 있다고 하자.

[1,2,3,5] # A

[4,6,7,8] # B

[] # C

각각 0번 인덱스를 비교하여, 더 작은 요소를 C로 넣어주고, 넣어 준 쪽의 cursor만 한 칸 이동한다.

[1,2,3,5] # A

[4,6,7,8] # B

[1] #C

이런식으로 되고, 반복적으로 각 cursor에 있는 값끼리 계속해서 비교하여 C에 넣어준다면 결과적으로 

C=[1,2,3,4,5,6,7,8] 이 된다.

 

merge sort의 기본 아이디어인 주어진 랜덤 배열을 하나씩 나눠주는 부분을 구현해 보았다.

 

 

다음으로는 나뉘어진 배열을 다시 정렬 하며 합치는 부분의 로직을 구현해 보았다.

 

 

이제 랜덤한 배열에 이 두개의 로직을 같이 적용 시키면 mergesort라고 할 수 있겠다.

def mergesort(lst):
    
    def scatter(lst):   # 분리시키는 함수
        if len(lst) <= 1:   # 1개씩 분리시킨다.
            return lst

        mid = len(lst) // 2 # 중간 index 기준
        left = lst[0:mid]   # 왼쪽 파트
        right = lst[mid:]   # 오른쪽 파트
        scatter(left)       # 왼쪽 재귀하여 파티션
        scatter(right)      # 오른쪽 재귀하여 파티션

        return merge(scatter(left), scatter(right)) #분리가 끝났다면 merge 함수로 간다.

    def merge(L, R):
        merged_lst = [] # 답을 낼 새로운 배열
        i = j = 0  # 각 L,R의 cursor
        while True:
            if L[i] < R[j]: # cursor 이동하면서 결과 리스트에 append
                merged_lst.append(L[i])
                i += 1
                if i == len(L):
                    merged_lst.extend(R[j:]) # 왼쪽 조각 리스트가 오른쪽보다 먼저 인덱싱이 끝난 경우
                    break
            else:
                merged_lst.append(R[j])
                j += 1
                if j == len(R):
                    merged_lst.extend(L[i:]) # 오른쪽 조각 리스트가 왼쪽보다 먼저 인덱싱이 끝난 경우
                    break

        return merged_lst

    return scatter(lst)


lst = [1, 7, 2, 5, 11, 21, 3, 4, 1111, 0]
print(mergesort(lst))

 

 

시간 복잡도?

 

  T(N) 을 N 의 길이를 정렬하기 위해 걸리는 시간이라고 하자. 위 그림의 예시처럼, 1단계 [1, 2, 3, 4, 5, 6, 7, 8] 을 정렬하기 위해 [1, 2, 3, 5] 과 [4, 6, 7, 8] 을 병합했다. 즉, 크기 N 인 배열을 정렬하기 위해 크기 N/2 인 부분 배열 2개를 비교 해보면 N/2 * 2 = N 번 비교하게 된다. 또한, 2단계 [1, 2, 3, 5] 과 [4, 6, 7, 8] 을 정렬하기 위해 [3, 5] [1, 2] 과 [6, 8] [4,7] 을 비교하였는데, 크기 N/2 인 부분 배열 2개를 정렬하기 위해 크기 N/4 인 부분 배열 4개를 비교 하였다. 이것으로 보았을때, 모든 단계에서 N 만큼 비교를 한다는 것을 알 수가 있다. 또한, 이진트리 형태의 k=log N이라고 할 수 있고, N만큼의 연산을 logN 번 반복한다고 하기 때문에 시간 복잡도는 O(N log N) 임을 알 수 있다.