정렬 - 병합 정렬(merge sort)

1. 병합 정렬(merge sort)란?

🖐 재귀를 활용

🖐 리스트를 반으로 자르고 각 부분을 정렬 -> 두 부분을 다시 정렬

 

 

2. 순서대로 생각하기

data = [1, 8, 4, 2] 일 때

👉 두 개로 자른다!  [1, 8] 과 [4, 2]
👉 앞부분을 자르고 다시 정렬해서 합친다! [1] [8] -> [1, 8]

👉 뒷부분을 자르고 다시 정렬해서 합친다! [4] [2] -> [2, 4]

👉 두 부분을 합친다! [1, 2, 4, 9]

     ( 1 < 2니까 [1] , 2<8니까 [1,2] ... )

 

✍ 단순히 잘라보자

def split_data(data):
    mid = int(len(data) / 2)  # 전체 길이의 반
    left = data[:mid]  # 반까지
    right = data[mid:]  # 그 뒤

✍ 재귀로 잘라보자

def mergesplit(data):
    if len(data) <= 1:  # 자른 부분의 갯수가 한개면 값을 그대로 리턴
        return data
    mid = int(len(data) / 2)  # 또 반으로 나누기
    left = mergesplit(data[:mid])
    right = mergesplit(data[mid:])  # 재귀
    return merge(left, right)  #아직 merge함수 작성안함

✍ 비교해보자

def merge(left, right):
    merged = []
    left_idx, right_idx = 0, 0
    
    # left / right 둘 다 있을 때
    while len(left) > left_idx and len(right) > right_idx:
        if left[left_idx] > right[right_idx]:  # 왼쪽 첫번째와 오른쪽 첫번째를 비교
            merged.append(right[right_idx])  # 오른쪽이 더 작으면 오른쪽(작은 수)를 리스트에 삽입
            right_idx += 1  # 인덱스를 옮겨줌
        else:  # 왼쪽이 더 작은 경우
            merged.append(left[left_idx])
            left_idx += 1
            
    # left 데이터가 없을 때
    while len(left) > left_idx:
        merged.append(left[left_idx])
        left_idx += 1
    
    # right 데이터가 없을 때
    while len(right) > right_idx:
        merged.append(right[right_idx])
        right_idx += 1
        
    return merged

 

3. 알고리즘 구현

def merge(left, right):
    merged = []
    left_idx, right_idx = 0, 0
    
    # left / right 둘 다 있을 때
    while len(left) > left_idx and len(right) > right_idx:
        if left[left_idx] > right[right_idx]:  # 왼쪽 첫번째와 오른쪽 첫번째를 비교
            merged.append(right[right_idx])  # 오른쪽이 더 작으면 오른쪽(작은 수)를 리스트에 삽입
            right_idx += 1  # 인덱스를 옮겨줌
        else:  # 왼쪽이 더 작은 경우
            merged.append(left[left_idx])
            left_idx += 1
            
    # left 데이터가 없을 때
    while len(left) > left_idx:
        merged.append(left[left_idx])
        left_idx += 1
    
    # right 데이터가 없을 때
    while len(right) > right_idx:
        merged.append(right[right_idx])
        right_idx += 1
        
    return merged

def mergesplit(data):
    if len(data) <= 1:  # 자른 부분의 갯수가 한개면 값을 그대로 리턴
        return data
    mid = int(len(data) / 2)  # 또 반으로 나누기
    left = mergesplit(data[:mid])
    right = mergesplit(data[mid:])  # 재귀
    return merge(left, right)
    
mergesplit([4,6,3,7,9,1])
# 출력 결과 : [1,3,4,6,7,9]

 

4. 복잡도

👉 각 단계는 항상 O(n)

👉 단계는 항상 log2n개 만큼 만들어짐

👉 즉 단계별 시간 복잡도 O(n) * O(logn) = O(nlogn)