[TIL] 병합정렬 - Merge Sort

병합 정렬

• 재귀를 사용
• 리스트를 반으로 나눈 후 각 리스트를 합병 정렬을 이용하여 정렬
• 리스트를 나누는 split 함수와 이를 다시 병합하는 merge함수가 필요

 

split 함수

 - 재귀용법을 이용하여 리스트를 반으로 나누는 함수

def split(data):
    if len(data) <=1:
        return data

    medium = int(len(data)/2)
    left = split(data[:medium])
    right = split(data[medium:])

    return merge(left, right)

 

merge 함수

 - left와 right로 나누어진 리스트를 다시 병합하는 함수

 - left와 right의 원소가 둘 다 남아있는 경우, left의 원소만 남아있는경우, right의 원소만 남아있는 경우의 세가지 경우를     고려하여 병합한다.

 

def merge(left, right):
    merged=[]
    l_point,r_point=0,0
    
    #left/right 원소 모두 존재
    while len(left)>l_point and len(right) >r_point:
        if left[l_point] > right[r_point]:
            merged.append(right[r_point])
            r_point+=1
        else:
            merged.append(left[l_point])
            l_point+=1

    #left 원소만 있을 때
    while len(left)>l_point:
        merged.append(left[l_point])
        l_point+=1

    #right 원소만 있을 때
    while len(right)>r_point:
        merged.append(right[r_point])
        r_point+=1

    return merged

 

병합정렬의 시간복잡도?
-O(nlogn)