[알고리즘] merge sort

✓ 새로운 리스트를 만들어 반환하는 경우 -> 메모리 많이 사용

def merge_sort1(arr):
    if len(arr) == 1:
        # result.append(li)
        return li

    m = len(arr) // 2
    left = merge_sort1(arr[0:m])
    right = merge_sort1(li[m:len(arr)])

    merged_list = []
    l = 0
    h = 0
    while l < len(left) and h < len(right):
        if left[l] < right[h]:
            merged_list.append(left[l])
            l += 1
        else:
            merged_list.append(right[h])
            h += 1
    merged_list += left[l:]
    merged_list += right[h:]

    return merged_list

 

 

✓ 기존 리스트의 배열을 바꾸는 경우 -> 메모리 최적화

def merge_sort(arr):    # in-place sort

    def sort(left, right):  # left: 왼쪽 배열의 시작 인덱스 / right: 오른쪽 배열의 끝 인덱스+1
        # 각 배열의 범위: left ~ mid-1 / mid ~ right-1
        if right - left < 2:  # 각 배열의 크기가 1이라면 각 배열 인덱스 차이는 1임
            return            # 우측 배열의 인덱스는 right-1 이니까 (right-1) - left < 1
                                # 조건을 만족하면 분할을 끝냄.

        mid = (left + right) // 2  # mid: 배열의 크기가 홀수든 짝수든 2로 나눈 몫

        sort(left, mid)     # 좌측 배열을 다시 분할, 입력에 의한 배열 범위는 left ~ mid-1
        sort(mid, right)    # 우측 배열을 다시 분할, 입력에 의한 배열 범위는 mid ~ right-1
        merge(left, mid, right)  # 각 sort 가 할 일이 끝나고( 크기가 1이 될 때까지 분할 )
        # 분할이 끝나는 시점의 left=0, mid=1, right=2
        # 우측 배열은 0번 인덱스, 좌측 배열은 1번 인텍스 가
        # 가장 먼저 merge 됨.

    def merge(left, mid, right):
        temp = []
        l_pointer = left
        r_pointer = mid     # 0 대신 전체 배열의 인덱스로 초기화
        # 포인터의 위치를 초기화시키고 각각을 하나씩 증가시키며 더 작은값이 생기면 temp에 추가
        while l_pointer < mid and r_pointer < right:    # 배열이 나눠짐을 인덱스로 표현
            if arr[l_pointer] < arr[r_pointer]: # 더 작은 값을 먼저 배치하기 위함
                temp.append(arr[l_pointer])
                l_pointer += 1
            else:
                temp.append(arr[r_pointer])
                r_pointer += 1

                # 위 동작과 여기까진 유사함
                # 새로운 배열 말고 target 배열 자체를 업데이트 해야함
                # 해당 stage에서 배치가 끝나고.

        # 위 반복문이 끝나면 l_pointer == mid 이거나 r_pointer == right 인 상태
        # 그래서 아래 두 반복문중 하나만 실행됨.
        while l_pointer < mid:  # 남은 구간은 무조건 다 작음. 무조건 아래 두 while중 하나만 실행됨
            temp.append(arr[l_pointer])
            l_pointer += 1
        while r_pointer < right:
            temp.append(arr[r_pointer])
            r_pointer += 1

        for i in range(left, right):
            arr[i] = temp[i - left]  # 어떤 구간이든 시작은 left니까

    return sort(0, len(arr))