[알고리즘/Python] 합병정렬 | merge sort

합병 정렬 [ Merge sort ] 

 

- 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하면서 정렬하는 방식

 

 

 

시간복잡도 ⏱

 

•     최선의 경우 : O(n log(n)) 
•     최악의 경우 : O(n log(n))
•     평균 : O(n log(n))

 

장점

 

1. 퀵 정렬은 Pivot을 어떻게 잡느냐에 따라 성능이 안좋아지는 경우가 있는데 그런 경우 업이 항상 O(n log(n))이라는 시간복잡도를 가짐

2. 안정한 정렬 - 제자리 정렬로 구현할 수 있기 때문에

 

단점

 

1. 추가적인 메모리가 필요하다. 정렬해야할 양이 많다면 메모리가 부담스러울 수 있다.

 

 

[ python merge sort code | 파이썬 합병 정렬 코드 ] 

def merge(alist):

    if len(alist) > 1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        merge(lefthalf)
        merge(righthalf)
        
        i,j,k = 0,0,0

        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] <righthalf[j]:
                alist[k] = lefthalf[i]
                i+=1
            else:
                alist[k] = righthalf[j]
                j+=1
            k+=1
        
        while i < len(lefthalf) :
            alist[k] = lefthalf[i]
            i+=1
            k+=1

        while j < len(righthalf) : 
            alist[k] = righthalf[j]
            j+=1
            k+=1


data = list(map(int,input("write down the list : ").split()))
    
merge(data)
print(data)

---

[ 힙 정렬 | Heap Sort ]

[ 선택정렬 | Selection Sort ]

[ 삽입정렬 | Insertion Sort ]

[ 퀵 정렬 | Quick Sort ]