merge_sort.py

def merge_sort(input_list: list) -> list:
    """Sort list using merge sort algorithm.
    :param input_list: list to be sorted.    
    :type input_list: list    
    :return: sorted list in ascending order.    
    :rtype: list    
    """    
    def merge(lst:list, p: int, q: int, r: int):
        """Helper function for merge sort: merge lst[p:q+1] and lst[q+1:r+1].
        :param lst: list to be sorted.        
        :param p: starting index of first sublist.        
        :param q: ending index of first sublist.        
        :param r: ending index of second sublist.        
        """        
        # Use copy() to avoid changing a and b when changing original list.        
        a = lst[p:q+1].copy()
        lena = q + 1 - p
        b = lst[q+1:r+1].copy()
        lenb = r - q
        # i and j remember progress in a and b.        
        i = 0        
        j = 0       
        # Fill lst[p:r+1]        
        for k in range(p,r+1):
            # a is all copied, just finish rest of b.            
            if i == lena:
                lst[k] = b[j]
                j += 1            
                # b is all copied, just finish rest of a.            
            elif j == lenb:
                lst[k] = a[i]
                i += 1            
            # a and b are both not done, need to compare.            
            elif a[i] < b[j]:
                lst[k] = a[i]
                i += 1           
            else:
                lst[k] = b[j]
                j += 1

    def inner_sort(lst: list, p: int, r:int):
        """Helper function for merge sort.
        :param lst: list to be sorted.        
        :type lst: list        
        :param p: starting index.        
        :type p: int        
        :param r: ending index (inclusive).        
        :type r: int        
        """        
        # if there is only 1 element, no need to sort.        
        if p < r:
            # Determine ending index of first sublist.            
            q = (p + r)//2            
            # Sort left sublist.            
            inner_sort(lst, p, q)
            # Sort right sublist.            
            inner_sort(lst, q+1, r)
            # Merge left and right sublists.            
            merge(lst, p, q, r)

    # Architecture of merge sort algorithm.    
    length = len(input_list)
    if length <= 1:
        return input_list
    else:
        inner_sort(input_list, 0, length - 1)
        return input_list