[Algorithm] 병합 정렬 (Merge Sort) .05

이번에 알아볼 알고리즘은 병합 정렬 (Merge Sort) 입니다.

합병정렬이라고도 불리며, 분할정복알고리즘 중 하나입니다. 또한 안정정렬에 속합니다.

🤔 과정 및 코드

반씩 나누는 걸 반복하여 1개가 될 때까지 나눈 후 이를 다시 병합(Merge)하면서 정렬해나갑니다.

 

 

📝 Python 예시 코드.

def merge(left, right):
    # 왼쪽 시작값 오른쪽 시작값, 병합하며 정리하기위한 빈 배열
    i = 0
    j = 0
    sorted_list = []

    while (i < len(left)) & (j < len(right)):
        # 무한반복하며 왼쪽배열과 오른쪽배열에서 가장왼쪽에 있는 값을 비교
        # (각 배열의 왼쪽에 있는 값이 최소값)

        #크기를 비요하여 작은 정렬하는 배열에 담음.
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1

    # 남은 배열 담음.
    while (i < len(left)):
        sorted_list.append(left[i])
        i += 1
    # 남은 배열 담음.
    while (j < len(right)):
        sorted_list.append(right[j])
        j += 1
    return sorted_list


def Merge_Sort(arr):

    # 길이가 1이라면, 더이상 나눌수 없음.
    if len(arr) <= 1:
        return arr

    # 중간 값을 구하고, 중간을 기준으로 좌우를 나눔.
    mid = len(arr)//2
    left = arr[:mid]
    right = arr[mid:]

    # 재귀함수로 반복하여 1개가 될때까지 나눔
    left_arr = Merge_Sort(left)
    right_arr = Merge_Sort(right)

    # 병합하면서 정렬함.
    return merge(left_arr, right_arr)

🕒 시간 복잡도.

반복의 수는 점점 절반으로 줄어들 기 때문에 O(logN) 시간이 필요하며, 각 패스에서 병합할 때 모든 값들을 비교해야 하므로 O(N) 시간이 소모됩니다. 따라서 총 시간 복잡도는 N*logN 이므로 O(NlogN)

 

💾 공간 복잡도.

병합 결과를 담을 배열이 추가로 필요합니다. 따라서 공간 복잡도는 O(N)

✋ 장점과 단점.

장점.

데이터와 상관없이 정렬되는 시간은 동일하다. O(NlogN)

 

단점.

추가 배열이 필요로하며, 제자리정렬이 아니다.

 

참조.

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

[알고리즘] 병합 정렬 - Merge Sort (Python, Java)