Merge sort

Quick sort 와 같이 분할, 정복, 병합의 루틴을 가지나 병합을 위해 새로운 collection을 생성한다는 점이 차이이다. 최악의 상황을 제외하면 일반적으로 Quick sort 성능이 더 뛰어나다.

def merge_sort(arr):
    def devide(arr):
        mid = int(len(arr) / 2)
        return arr[0:mid], arr[mid:]
    def merge(left, right):
        ind_l = ind_r = 0
        new_arr = []
        while ind_l < len(left) or ind_r < len(right):
            if ind_l >= len(left) and ind_r < len(right):
                new_arr.append(right[ind_r])
                ind_r += 1
            elif ind_l < len(left) and ind_r >= len(right):
                new_arr.append(left[ind_l])
                ind_l += 1
            else:
                if left[ind_l] <= right[ind_r]:
                    new_arr.append(left[ind_l])
                    ind_l += 1
                else:
                    new_arr.append(right[ind_r])
                    ind_r += 1

        return new_arr

    if len(arr) > 1:
        left, right = devide(arr)
        left = merge_sort(left)
        right = merge_sort(right)
        new_arr = merge(left, right)
        return new_arr
    else:
        return arr