merge sort - 병합 정렬

재귀 용법을 활용한 정렬 알고리즘이다.

1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

알고리즘의 이해

데이터가 4개일때

예 ) data = [1, 9, 3, 2]

1. 먼저 [1, 9], [3, 2] 로 나눈다.
2. 다시 [1,9]를 [1], [9]로 나눈다.
3. 나눈 [1], [9]를 정렬하여 [1, 9]로 합친다.
4. 다음 [3, 2]를 [3], [2]로 나눈다.
5. 나눈 [3], [2]를 정렬하여 [2, 3]으로 합친다.
6. [1,9]와 [2,3]을 정렬하여 합친다.
   1. 1 < 2 이니 [1]
   2. 9 > 2 이니 [1, 2]
   3. 9 > 3 이니 [1, 2, 3]
   4. 9밖에 없으니 [1, 2, 3, 9]

 

완성 코드

import random


def split(list_data):
    if len(list_data) < 1:
        return list_data

    mid_index = len(list_data) // 2

    left_list = split(list_data[:mid_index])
    right_list = split(list_data[mid_index:])

    return merge(left_list, right_list)


def merge(left_list, right_list):
    left_start_index, right_start_index = 0, 0
    temp_list = list()

    while len(left_list) > left_start_index and len(right_list) > right_start_index:

        if left_list[left_start_index] < right_list[right_start_index]:
            temp_list.append(left_list[left_start_index])
            left_start_index += 1

        else:
            temp_list.append(right_list[right_start_index])
            right_start_index += 1

    while len(left_list) > left_start_index:
        temp_list.append(left_list[left_start_index])
        left_start_index += 1

    while len(right_list) > right_start_index:
        temp_list.append(right_list[right_start_index])
        right_start_index += 1

    return temp_list


def merge_sort(list_data):
    return split(list_data)


if __name__ == '__main__':
    data = random.sample(range(1000), 15)

    print(data)

    print(merge_sort(data))