merge_sort_topdown.py

#---------------------------------------------------------------
# Merge sort - top down
#---------------------------------------------------------------

# https://leetcode.com/explore/learn/card/recursion-ii/470/divide-and-conquer/2868/
# https://rust-algo.club/sorting/mergesort/

"""

Time complexity

    Best : O(N Log N)
    Avg : O(N Log N)
    Worst : O(N Log N)`


Space complexity

    O(N)

"""

def merge_sort(nums):
    # bottom cases: empty or list of a single element.
    if len(nums) <= 1:
        return nums

    pivot = int(len(nums) / 2)
    left_list = merge_sort(nums[0:pivot])
    right_list = merge_sort(nums[pivot:])
    return merge(left_list, right_list)


def merge(left_list, right_list):
    left_cursor = right_cursor = 0
    ret = []
    while left_cursor < len(left_list) and right_cursor < len(right_list):
        if left_list[left_cursor] < right_list[right_cursor]:
            ret.append(left_list[left_cursor])
            left_cursor += 1
        else:
            ret.append(right_list[right_cursor])
            right_cursor += 1
    
    # append what is remained in either of the lists
    ret.extend(left_list[left_cursor:])
    ret.extend(right_list[right_cursor:])
    
    return ret