def merge_sort(nums: list) -> list:
    """Sort an array using the merge sort algorithm.

    Args:
        nums (list): The unsorted input array.

    Returns:
        list: The sorted output array.
    """

    def split_array(nums: list) -> list:
        """Recursively split array in half.

        Args:
            nums (list): The unsorted input array.

        Returns:
            list: Returns a sorted array.
        """
        if len(nums) <= 1:
            return nums

        mid = len(nums) // 2

        left = split_array(nums[:mid])
        right = split_array(nums[mid:])

        return merge_two(left, right)

    def merge_two(a: list, b: list) -> list:
        """Merges two sorted arrays.

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

        Returns:
            list: Returns sorted array containing all elements from a and b.
        """
        result = []
        i = j = 0
        while i < len(a) and j < len(b):
            if a[i] <= b[j]:
                result.append(a[i])
                i += 1
            else:
                result.append(b[j])
                j += 1
        while i < len(a):
            result.append(a[i])
            i += 1
        while j < len(b):
            result.append(b[j])
            j += 1
        return result

    return split_array(nums)