[고급정렬 ]: 병합정렬

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

• 안정 정렬에 속하며 대표적인 분할정복 알고리즘중 하나이다.
  • 분할정복이란?
    • 분할정복은 일반적으로 재귀 호출을 사용한다.
    • devide : 문제를 한개 또는 둘 이상으로 나눈다 
    • conquer : 나누어진 문제가 충분히 작고 해결 가능하다면 해결한다.
    • devide 와 conquer 를 반복하며 결과를 합쳐서 문제를 해결한다
  • 과정
    1.  리스트의 길이가 1일때 가지 두개로 양분하여 분할한다. (재귀 호출)
    2.  길이가 충분해졌다면 해당 리스트들을 정렬하여 합친다.
  • 시간복잡도
    •  O(nlogn) 을 갖게된다.

 

 

 

 

 

병합 정렬(merge sort) 예제 코드(파이썬)

# 병합정렬

def splite_merge(lst:list):
    if len(lst) < 2:
        return lst
    
    else:
        lenght = len(lst)//2
        left , right = lst[:lenght] ,lst[lenght:]
        return merge(splite_merge(left)  , splite_merge(right))



def merge (right , left):
    right_cnt , left_cnt = 0, 0
    lst = []
    while (left_cnt < len(left) and right_cnt < len(right)):
        if right[right_cnt] < left[left_cnt]:
            lst.append(right[right_cnt])
            right_cnt += 1
        else:
            lst.append(left[left_cnt])
            left_cnt += 1
    if left_cnt != len(left) :
        lst.extend(left[left_cnt:])
    else :
        lst.extend(right[right_cnt:])
    return lst




import random
lst = random.sample(range(50) , 40)
#print(lst)
print(splite_merge(lst))