병합정렬 (Merge sort)

병합정렬

• 배열을 절반으로 잘라 나눈다. (분리 단계)
• 잘라서 나눈 배열을 재귀적으로 병합정렬 시킨다. (병합 단계)

예시로 이해

• [2, 8, 6, 4]
• [2, 8], [6, 4]
• [2], [8] | [6], [4]
• 앞 두 배열을 정렬하여 합친다. -> [2, 8]
• 뒤 두 배열을 정렬하여 합친다. -> [4, 6]
• [2, 8]과 [4, 6]을 합친다.
  • 2 < 4 -> [2] 남은 배열: [8], [4, 6]
  • 8 > 4 -> [2, 4] 남은 배열: [8], [6]
  • 8 > 6 -> [2, 4, 6] 남은 배열: [8]
  • [2, 4, 6, 8]

구현

from turtle import right


def split(array):
    if len(array) <= 1:
        return array

    split_point = len(array) // 2
    
    left_array = array[:split_point]
    right_array = array[split_point:]
    return merge(split(left_array), split(right_array))

def merge(left_array, right_array):
    l_idx = 0
    r_idx = 0
    sorted_array = []
    
    while (l_idx < len(left_array)) and (r_idx < len(right_array)):
        if left_array[l_idx] < right_array[r_idx]:
            sorted_array.append(left_array[l_idx])
            l_idx += 1
        else:
            sorted_array.append(right_array[r_idx])
            r_idx += 1

    if l_idx == len(left_array):
        sorted_array.extend(right_array[r_idx:])

    if r_idx == len(right_array):
        sorted_array.extend(left_array[l_idx:])
    
    return sorted_array

if __name__ == "__main__":
    l = [10, 93, 25, 784, 21, 16, 132, 47, 35]
    
    r = split(l)
    print(l)
    print(r)