합병/병합 정렬(merge sort)

분할 정복 알고리즘의 대표적인 예

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

* 시간 복잡도 : O(n log n) (= O(n) (각 단계의 노드 길이) * O(log n) (단계의 깊이))
  - 문제에서 데이터 개수가 최대 1,000,000개, 제한 시간 2초 이내라면
    시간 복잡도가 위와 같은 O(n logn)의 정렬 알고리즘을 이용해야 함
    (2^10 = 약 1,000이므로 n=1,000,000일 때, n logn = 20,000,000이고,
    파이썬에서는 1초에 2천~5천만 번의 연산이 가능하므로 제한에 걸리지 않는다(간신히 통과할 수도 있음))

def merge_split(data):
    if len(data) <= 1:
        return data

    mid = int(len(data) / 2)
    left = merge_split(data[:mid])
    right = merge_split(data[mid:])
    return merge(left, right)

def merge(left, right):
    merged = []
    l_pointer, r_pointer = 0, 0
    
    """ case1: left/right 아직 남아 있을 때 """
    while len(left) > l_pointer and len(right) > r_pointer:
        if left[l_pointer] > right[r_pointer]:
            merged.append(right[r_pointer])
            r_pointer += 1
        else:
            merged.append(left[l_pointer])
            l_pointer += 1   

    """ case2: left만 남아있을 때 """
    while len(left) > l_pointer:
        merged.append(left[l_point])
        l_pointer += 1

    """ case3: right만 남아있을 때 """
    while len(right) > r_pointer:
        merged.append(right[r_pointer])
        r_pointer += 1
    return merged

data = [5,6,3,2]
print(merge_split(data)) 
""" [2, 3, 5, 6] """

    출처 : fastcampus