병합 정렬 알고리즘

• 정렬되지 않은 리스트를 절반으로 잘라 비슷한 두 리스트로 나눈다.
• 각 부분의 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다
• 두 리스트를 다시 하나의 리스트로 합병한다.
• 시간 복잡도는 O(n log n)

출처: [위키피디아]

나의 정의

• 리스트를 0또는 1이 될 때까지 반으로 나누고, 그것들을 두 리스트씩 포인터를 가지고 하나의 리스트로 정렬하는 것
• 즉 재귀적으로 길이가 0또는 1까지 나누고 결국 합치는 것
• 함수는 2개가 필요

if문을 이용한 병합 정렬

def split(li):
    if len(li) <= 1:
        return li
    mid_idx = len(li)//2
    left_list = split(li[:mid_idx])
    right_list = split(li[mid_idx:])
    return merge(left_list, right_list)
def merge(left_list, right_list):
    total = []
    lp = 0
    rp = 0
    for _ in range(len(left_list) + len(right_list)):
        if lp == len(left_list):
            total.append(right_list[rp])
            rp += 1
        elif rp == len(left_list):
            total.append(left_list[lp])
            lp += 1
        elif left_list[lp] > right_list[rp]:
            total.append(right_list[rp])
            rp += 1
        elif left_list[lp] < right_list[rp]:
            total.append(left_list[lp])
            lp += 1
    return total

print(split([3,2,5,4,1,6,9]))

[1, 2, 3, 4, 5, 6, 9]

while문을 이용한 병합 정렬

def merge(left_list, right_list):
    merged = list()
    left_point, right_point = 0, 0
    
    #왼쪽 오른쪽 둘다 있을 때
    while len(left_list) > left_point and len(right_list) > right_point:
        if left_list[left_point] < right_list[right_point]:
            merged.append(left_list[left_point])
            left_point += 1
        else:
            merged.append(right_list[right_point])
            right_point += 1
            
    #왼쪽 데이터만 있을 때  >> 넣기
    while len(left_list) > left_point:
        merged.append(left_list[left_point])
        left_point += 1
        
    #오른쪽 데이터만 남았을 때 >> 넣기
    while len(right_list) > right_point:
        merged.append(right_list[right_point])
        right_point += 1
        
    return merged

def mergesplit(data):
    if len(data) <= 1:
        return data
    
    mid_point = len(data)//2
    left_list = mergesplit(data[:mid_point])
    right_list = mergesplit(data[mid_point:])

    return merge(left_list,right_list)