6. 병합정렬(Merge sort)

 

# 1. 병합정렬(merge sort)
* 재귀 용법을 활용한 정렬 알고리즘
* 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눔
* 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬
* 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병


#2. 알고리즘 이해하기

'''
data_list = [1, 9, 3, 2]
'''

1. [1,9] 로 나눔
2. 앞부분은 [1], [9]로 나누고 뒷부분은 [3],[2]로 나눔
3. 정렬해서 합침 [1,9] , [2, 3]
4. [1,9] , [2, 3] 을 합침(단, 아래와 같은 조건으로)
  * 1 < 2 이므로 리스트 1을 저장 [1]
  * 9 > 2 이므로 리스트에 2를 추가 [1,2]
  * 9 > 3 이므로 리스트에 3을 추가 [1,2,3]
  * 9 밖에 없으니 리스트에 9를 추가 [1,2,3,9]
  

#3. 알고리즘 구현하기
#3-1. mergesplit 함수
* 만약 리스트 갯수가 1개면 해당값을 리턴
* 그렇지 않으면 리스트를 앞 뒤 두개로 나눔(절반)


def mergesplit(data):
  medium = int(len(data)/2)
  left = data[:medium]
  right = data[medium:]
  print(left, right)

mergesplit([1, 5, 3, 2, 4, 10])
-->
[1, 5, 3] [2, 4, 10]


# 3-2. merge 함수
* 리스트 변수 하나 만듦(sorted)
* left_index, right_index = 0
* left와 right를 확인하여 값을 비교
* 만약 left_index나 right_index가 이미 left 또는 right 리스트 모두 순회했다면 그 반대 쪽 데이터를 그대로 넣고 해당 인덱스를 1 증가


def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data)/2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)
def merge(left, right):
    merged = list()
    left_index, right_index = 0, 0
    # left, right의 데이터가 모두 있을 때
    while len(left) > left_index and len(right) > right_index:
        if left[left_index] > right[right_index]:
            merged.append(right[right_index])
            right_index += 1
        else:
            merged.append(left[left_index])
            left_index += 1
    # right 데이터가 없을 때
    while len(left) > left_index:
        merged.append(left[left_index])
        left_index += 1
    # left 데이터가 없을 때
    while len(right) > right_index:
        merged.append(right[right_index])
        right_index += 1
    return merged
    
import random
data_list = random.sample(range(100), 10)
print(data_list)
mergesplit(data_list)
-->
[77, 23, 98, 34, 32, 29, 6, 17, 61, 60]
[6, 17, 23, 29, 32, 34, 60, 61, 77, 98]