병합 정렬

☝ 병합 정렬은 더 이상 나눠지지 않을 때까지 배열을 둘로 나눈 후, 작은 것부터 순서대로 합치는 정렬이다.

🎫 개념

병합 정렬은 분할 정복 개념을 이용한다. 정렬하고자 하는 데이터를 더 이상 나눠지지 않을 때까지 계속 둘로 나눠준 후, 더 이상 나눌 수 없으면 2개씩 합친다. 이때 합치고자 하는 두 배열 중 작은 데이터부터 합쳐준다.

❓ 예시

input = [2,5,4,3,1,8,7,6]
✔ step1
[2,5,4,3], [1,8,7,6]

✔ step2
[2,5], [4,3], [1,8], [7,6]

✔ step3
[2], [5], [4], [3], [1], [8], [7], [6]

✔ step4
[2,5], [3,4], [1,8], [6,7]

✔ step5
[2,3,4,5], [1,6,7,8]

✔ step6
[1,2,3,4,5,6,7,8]

💻 병합 정렬 코드 구현 (python)

def merge_sort(arr):
    if len(arr) < 2:
        return arr
    #더 이상 분할 할 수 없을 때까지 데이터를 둘로 분할 해줌
    m = len(arr)//2
    l_arr = merge_sort(arr[:m])
    r_arr = merge_sort(arr[m:])
    merged_arr = []
    l, r = 0, 0

    #합치고자 하는 두 리스트의 값 중 가장 작은 값을 먼저 나열한다.
    while l < len(l_arr) and r < len(r_arr):
        if l_arr[l] < r_arr[r]:
            merged_arr.append(l_arr[l])
            l += 1
        else:
            merged_arr.append(r_arr[r])
            r += 1

    #위의 while문에서 둘 중 먼저 정렬이 끝난 리스트가 있으면 나머지 요소들과 함께 병합한다.
    merged_arr += l_arr[l:]
    merged_arr += r_arr[r:]
    return merged_arr

if __name__ == '__main__' :
    arr = list(map(int, input().split()))
    print(merge_sort(arr))

⏰ 시간 복잡도

분할 정복을 사용하는 병합 정렬은 우선, 절반씩 분할하기 때문에 O(logn)의 시간이 걸린다.
그리고 병합 할 때 가장 작은 값부터 정렬하기 위해 모든 값을 탐색하므로 O(n)의 시간이 걸린다. 따라서 O(nlogn)의 시간 복잡도를 갖는다.