[알고리즘][정렬] 병합 정렬 - Merge Sort

🙆‍♂️병합 정렬

---

병합정렬은 분활하고 정렬하고 합병하는 그런 정렬입니다.

 

 

🙋‍♂️방식

---

먼저 이렇게 배열이 있따면 배열의 길이가 1이 될 때 까지 나눕니다.

 

그리고 정렬과 합병을 반복하면 됩니다. 시간 복잡도는 O(n log n) 입니다.

 

def merge(arr):
    if len(arr) == 1:
        return arr

#####나누는 구간#####
    middle = len(arr)//2

    left_arr = arr[:middle]
    right_arr = arr[middle:]

    leftArrSort = merge(left_arr)
    rightArrSort = merge(right_arr)

    leftIdx = 0
    rightIdx = 0



#####합치는 구간#####
    sortArr = []

    while leftIdx < len(leftArrSort) or rightIdx < len(rightArrSort):
        if leftIdx == len(leftArrSort):
            sortArr.append(rightArrSort[rightIdx])
            rightIdx+=1
            continue
        if rightIdx == len(rightArrSort):
            sortArr.append(leftArrSort[leftIdx])
            leftIdx+=1
            continue
        if leftArrSort[leftIdx] <= rightArrSort[rightIdx]:
            sortArr.append(leftArrSort[leftIdx])
            leftIdx+=1
        else:
            sortArr.append(rightArrSort[rightIdx])
            rightIdx+=1
            continue
    
    return sortArr