[Python] 병합 정렬(merge sort)

 

• 분할 정복 알고리즘 중 하나로 병합 정렬(merge sort) 또는 합병 정렬이라고 부른다.
• 정렬되지 않은 전체 데이터를 하나의 단위로 분할한 후 분할한 데이터들을 다시 병합하면서 정렬하는 방식이다.
• 간단히 설명하자면, 큰 데이터를 하나의 작은 데이터로 쪼갠 후 정렬하면서 다시 합치는 것이다.
• 시간 복잡도는 O(n*logn)이다.

 

merge sort

 

포인트

1. 분할: 배열이 하나의 원소가 될때 까지 절반으로 나눈다.

 

2. 병합: 분할된 각각의 원소를 비교하여 정렬된 배열을 만든다.

 

 

Python Code

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)
    
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

 

Code 결과 확인하기

import random

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

res = mergesplit(data_list)
print(res)

# [34, 51, 67, 6, 79, 17, 23, 64, 84, 12]
# [6, 12, 17, 23, 34, 51, 64, 67, 79, 84]

 

 

문제 풀어보기

• 문제를 풀어보면서 병합 정렬(merge sort)를 이해해보자.

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

 

 

 

 

---

Reference

• Engineering Blog by Dale Seo
• naver blog by 안경잡이개발자