


def 							_UpperCAmelCase    (UpperCamelCase__					:  list[int]						):







       if len(_UpperCAmelCase						) > 1:
              _A				:	List[str]       =			len(_UpperCAmelCase						) // 2  # Finds the middle of the array
              _A				:	Tuple       =			arr[
                  :middle_length
              ]  # Creates an array of the elements in the first half.
              _A				:	Union[str, Any]       =			arr[
                  middle_length:
              ]  # Creates an array of the elements in the second half.
              _A				:	List[str]       =			len(_UpperCAmelCase						)
              _A				:	Dict       =			len(_UpperCAmelCase						)
              merge(_UpperCAmelCase						)  # Starts sorting the left.
              merge(_UpperCAmelCase						)  # Starts sorting the right
              _A				:	Dict       =			0  # Left Counter
              _A				:	Optional[int]       =			0  # Right Counter
              _A				:	List[Any]       =			0  # Position Counter
              while (
                  left_index < left_size and right_index < right_size
              ):  # Runs until the lowers size of the left and right are sorted.
                     if left_array[left_index] < right_array[right_index]:
                            _A				:	List[str]       =			left_array[left_index]
                            left_index += 1
                     else:
                            _A				:	str       =			right_array[right_index]
                            right_index += 1
                     index += 1
              while (
                  left_index < left_size
              ):  # Adds the left over elements in the left half of the array
                     _A				:	Tuple       =			left_array[left_index]
                     left_index += 1
                     index += 1
              while (
                  right_index < right_size
              ):  # Adds the left over elements in the right half of the array
                     _A				:	str       =			right_array[right_index]
                     right_index += 1
                     index += 1
       return arr


if __name__ == "__main__":
    import doctest

    doctest.testmod()




from __future__ import annotations

from typing import Any







class 					lowerCAmelCase__	:




     '''simple docstring'''


     def __init__(						self			,						__lowerCamelCase			,						__lowerCamelCase)      ->    None:  # noqa: A002
            _A				:	List[str]       =			item
            _A				:	List[Any]       =			next







class 					lowerCAmelCase__	:




     '''simple docstring'''


     def __init__(						self)      ->    None:
            _A				:	Node | None       =			None
            _A				:	List[Any]       =			0


     def 			_lowerCamelCase			(						self			,						__lowerCamelCase)      ->    None:
            _A				:	Union[str, Any]       =			Node(__lowerCamelCase			,						self.head)
            self.size += 1


     def 			_lowerCamelCase			(						self)      ->    Any:
            # Switched 'self.is_empty()' to 'self.head is None'
            # because mypy was considering the possibility that 'self.head'
            # can be None in below else part and giving error
            if self.head is None:
                   return None
            else:
                   _A				:	str       =			self.head.item
                   _A				:	List[Any]       =			self.head.next
                   self.size -= 1
                   return item


     def 			_lowerCamelCase			(						self)      ->    bool:
            return self.head is None


     def __str__(						self)      ->    str:
            if self.is_empty():
                   return ""
            else:
                   _A				:	List[str]       =			self.head
                   _A				:	Optional[int]       =			""
                   _A				:	list[str]       =			[]
                   while iterate:
                          item_list.append(str(iterate.item))
                          _A				:	Optional[Any]       =			iterate.next

                   _A				:	List[str]       =			" --> ".join(__lowerCamelCase)

                   return item_str


     def __len__(						self)      ->    int:
            return self.size
