Cell 12

def mergesort(nums):
    """Mergesort."""
    def merge(a, b):
        i, j, merged, m, n = 0, 0, [], len(a), len(b)
        while i < m and j < n:
            if a[i] < b[j]:
                merged.append(a[i])
                i += 1
            else:
                merged.append(b[j])
                j += 1
        return merged + a[i:] + b[j:]
    if len(nums) < 2:
        return nums
    a = mergesort(nums[:len(nums)//2])
    b = mergesort(nums[len(nums)//2:])
    return merge(a, b)
    
a = [2, 9, 2, 3, 5, 8, 1]
assert mergesort(a) == [1, 2, 2, 3, 5, 8, 9]
print('All passed!')

What the code could have been:

python
def merge_sort(nums: list) -> list:
    """
    Sort a list of numbers using the merge sort algorithm.

    Args:
        nums (list): The list of numbers to be sorted.

    Returns:
        list: The sorted list of numbers.
    """

    def merge(a: list, b: list) -> list:
        """
        Merge two sorted lists into a single sorted list.

        Args:
            a (list): The first sorted list.
            b (list): The second sorted list.

        Returns:
            list: The merged sorted list.
        """
        merged = []
        i, j = 0, 0

        # Merge smaller elements first
        while i < len(a) and j < len(b):
            if a[i] < b[j]:
                merged.append(a[i])
                i += 1
            else:
                merged.append(b[j])
                j += 1

        # Append any remaining elements
        merged += a[i:]
        merged += b[j:]

        return merged

    if len(nums) <= 1:  # Base case: lists with 1 or 0 elements are already sorted
        return nums

    # Recursively split the list into two halves
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])

    # Merge the two sorted halves
    return merge(left, right)


a = [2, 9, 2, 3, 5, 8, 1]
assert merge_sort(a) == [1, 2, 2, 3, 5, 8, 9]
print('All passed!')