합병 정렬

** 개요

 

 

** 설명

크게 작은 단위로 나누어서, 

위로 올라오며 합치는 방식이라고 생각하시면 됩니다.

예시 )

[1, 2, 3, 5]  # 정렬된 배열 A
[4, 6, 7, 8]  # 정렬된 배열 B
[] # 두 집합을 합칠 빈 배열 C

        ↓
1단계 : [**1**, 2, 3, 5] 
        ↓
       [**4**, 6, 7, 8] 
        1과 4를 비교합니다!
        1 < 4 이므로 1을 C 에 넣습니다.
     C:[1]

           ↓
2단계 : [1, **2**, 3, 5] 
        ↓
       [**4**, 6, 7, 8] 
        2와 4를 비교합니다!
        2 < 4 이므로 2를 C 에 넣습니다.
     C:[1, 2]

              ↓
3단계 : [1, 2, **3**, 5] 
        ↓
       [**4**, 6, 7, 8] 
        3과 4를 비교합니다!
        3 < 4 이므로 3을 C 에 넣습니다.
     C:[1, 2, 3]

                 ↓
3단계 : [1, 2, 3, **5**] 
        ↓
       [**4**, 6, 7, 8] 
        5와 4를 비교합니다!
        5 > 4 이므로 4을 C 에 넣습니다.
     C:[1, 2, 3, 4]

                 ↓
3단계 : [1, 2, 3, **5**] 
           ↓
       [4, **6**, 7, 8] 
        5와 6을 비교합니다!
        5 < 6 이므로 5을 C 에 넣습니다.
     C:[1, 2, 3, 4, 5]

엇, 이렇게 되면 A 의 모든 원소는 끝났습니다!

그러면 B에서 안 들어간 원소인
       [6, 7, 8] 은 어떡할까요?
하나씩 C 에 추가해주면 됩니다.
     C:[1, 2, 3, 4, 5, 6, 7, 8] 이렇게요!

그러면 A 와 B를 합치면서 정렬할 수 있었습니다.

** 구현

from typing import List


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        #쪼개고
        def splice(lst):
            if len(lst) <= 1:
                return lst
            mid = len(lst) //2
            L = lst[:mid]
            R = lst[mid:]
            oneL = splice(L)
            oneR = splice(R)
            sorted_lst = sort_pieces(oneL, oneR)
            return sorted_lst
        #쪼갠 걸 정렬하며 합친다
        #[8], [4,5]
        def sort_pieces(oneL, oneR):
            i = 0
            j = 0
            new = []
            while i < len(oneL) and j < len(oneR):
                if oneL[i] < oneR[j]:
                    new.append(oneL[i])
                    i+=1
                else:
                    new.append(oneR[j])
                    j += 1

            while j == len(oneR) and i < len(oneL):
                new.append(oneL[i])
                i += 1

            while i == len(oneL) and j < len(oneR):
                new.append(oneR[j])
                j+=1
            return new

        return splice(intervals)


aa = Solution()
print(aa.merge([[1,3],[2,6],[8,10],[15,18]]))

 

** 시간 복잡도

 

위의 케이스에서 보듯이, 각각의 레벨에서는 N만큼 탐색을 합니다.

그 이유는 ,

계속 절반으로 나누면 그 절반들을 서로 비교하는 과정이 반복되기 때문인데요,

[8,7,6,5,4,3,2,1]이 있다고 치면, [8,7,6,5]와 [4,3,2,1]을 탐색해도 8번 봅니다.

(방금 예시는 정확하게 8번은 아니지만, 모든 데이터가 깔끔하게 정렬되어있지는 않습니다.)

 

그렇다면 아래로 몇 단계까지 내려가는지를 알면 시간 복잡도가 나오는데요,

 N > N/2 > N/4 > N/8 ......1

총 log2 N번 반복하면 1이 됩니다.

 

따라서 시간 복잡도는 O(Nlog2N)이 됩니다.

 

** 관련 문제

https://leetcode.com/problems/sort-an-array/

Sort an Array - LeetCode