Merge Sort

Sorting algorithm

divide & conquer algorithm

 

 

 

시간복잡도

 

 

 

merge sort structure

 

 

 

 

각 층의 계산 시간 : 데이터 개수가 n일 때, 이를 정렬하는 데 cn의 시간이 걸린다고 해보자(c는 컴퓨팅 파워 등과 관계 있는 어떤 상수를 나타냄). 

 

층의 수 :  logn

 

Big-O notation : O(nlogn)

 

 

 

Python Code

def merge(left, right):
    result = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:]
    return result
 
 
def merge_sort(ls):
    if len(ls) <= 1:
        return ls
    mid = len(ls) // 2
    leftlist = ls[:mid]
    rightlist = ls[mid:]
    leftlist = merge_sort(leftlist)
    rightlist = merge_sort(rightlist)
    return merge(leftlist, rightlist)

 

 

 

참고 출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/03/mergesort/

합병정렬(Merge Sort) · ratsgo's blog