[Algorithm] 병합 정렬 (python)

병합 정렬

주어진 데이터를 잘게 나누고, 잘게 나눈 데이터들을 합치면서 정렬해가며 최종적으로 정렬된 데이터를 도출하는 방식

array = [5, 3, 2, 1, 6, 8, 7, 4]

# 병합 정렬
def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = array[:mid]
    right_array = array[mid:]
    return merge(merge_sort(left_array), merge_sort(right_array))

# 나눠진 데이터들을 병합
def merge(array1, array2):
    result = []         # 정렬된 데이터를 담을 장소
    array1_index = 0
    array2_index = 0

    while array1_index < len(array1) and array2_index < len(array2):
        # array1의 원소가 더 작다
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        # array2의 원소가 더 작다
        else:
            result.append(array2[array2_index])
            array2_index += 1

    # array1의 남은 원소가 없다.
    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    # array2의 남은 원소가 없다.
    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result



print(merge_sort(array))

print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge_sort([-7, -1, 9, 40, 5, 6, 10, 11]))
print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge_sort([-1, 2, 3, 5, 40, 10, 78, 100]))
print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge_sort([-1, -1, 0, 1, 6, 9, 10]))

• 재귀를 통해 주어진 데이터를 잘게 쪼개고, 쪼개진 데이터들을 병합하면서 정렬한다

[출력]
[1, 2, 3, 4, 5, 6, 7, 8]
정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 =  [-7, -1, 5, 6, 9, 10, 11, 40]
정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 =  [-1, 2, 3, 5, 10, 40, 78, 100]
정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 =  [-1, -1, 0, 1, 6, 9, 10]

시간 복잡도

• O(nlogn)