병합 정렬(merge sort) 알고리즘

1. 병합 정렬(merge sort)

-> 재귀용법을 활용한 정렬 알고리즘

• 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
• 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
• 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다

2. 알고리즘 이해

• data_list = [1,9,3,2]
  • [1,9]       [3,2]
  • [1] [9]
  • 다시 정렬해서 합침   [1, 9]
  • [3] [2]
  • 다시 정렬해서 합침   [2, 3]
  • [1, 9]    [2, 3] 합침
    • [1] 
    • [9] > [2]   =>  [1 , 2] 
    • [9] > [3]    => [1, 2, 3]
    • [1, 2, 3, 9]

3. 구현

<mergesplit 함수 만들기>

• 리스트 개수가 1개 -> 해당 값 리턴
• 아니면                      -> 리스트 앞, 뒤 2개로 나누기
• left = mergesplit(앞)
• right = mergesplit(뒤)
• merge(left, right)

def mergesplit(data):
	if len(data) <= 1:
    	return data
    m = int(len(data) / 2)
    left = mergesplit(data[:m])
    right = mergesplit(data[m:])
    return merge(left, right)

 

<merge 함수 만들기>

• 목표: left 와 right 의 리스트 데이터를 정렬해서 sorted_list 라는 이름으로 return 하기
• left와 right는 이미 정렬된 상태 또는 데이터가 하나임

• 리스트 변수 하나 만들기 -> sorted
• left_idx , rigth_idx = 0
• while left_idx < len(left)   or  right_idx < len(right):
  • 만약, left_idx 나 right_idx 가 이미  left 또는 right 리스트를 다 순회했다면, 
    그 반대쪽 데이터를 그대로 넣고, 해당 인덱스 1 증가
  • if left[left_idx] < right[right_idx]:
         sorted.append(left[left_idx])
         left_idx += 1
  • else:
         sorted.append(right[right_idx])
         rigth_idx += 1

def merge(left, right):
	merged = list()
    left_p , right_p = 0, 0
    
    #left/right 둘 다 존재
    while len(left) > left_p and len(right) > right_p:
    	if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    #left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    #right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged

---

최종 코드

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    #left/right 둘다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    #left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    #right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged


def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

import random

data_list = random.sample(range(100), 10)
mergesplit(data_list)

>>>[13, 17, 28, 30, 36, 45, 48, 65, 70, 73]

4. 알고리즘 분석

• 따라서, 각 단계는 항상 O(n) 
• 단계는 항상 𝑙𝑜𝑔2𝑛개 만큼 만들어짐, 시간 복잡도는 결국 O(log n), 2는 역시 상수이므로 삭제
• 따라서, 단계별 시간 복잡도 O(n) * O(log n) = O(n log n)