"""simple docstring"""




def 				__a       (			_lowercase						):







					"""simple docstring"""





					if len(__UpperCAmelCase						) > 1:
										lowerCamelCase__		:   Dict  				=					len(__UpperCAmelCase						) // 2  # Finds the middle of the array
										lowerCamelCase__		:   List[str]  				=					arr[
										    :middle_length
										]  # Creates an array of the elements in the first half.
										lowerCamelCase__		:   Optional[int]  				=					arr[
										    middle_length:
										]  # Creates an array of the elements in the second half.
										lowerCamelCase__		:   Optional[Any]  				=					len(__UpperCAmelCase						)
										lowerCamelCase__		:   Optional[int]  				=					len(__UpperCAmelCase						)
										merge(__UpperCAmelCase						)  # Starts sorting the left.
										merge(__UpperCAmelCase						)  # Starts sorting the right
										lowerCamelCase__		:   Dict  				=					0  # Left Counter
										lowerCamelCase__		:   List[str]  				=					0  # Right Counter
										lowerCamelCase__		:   Optional[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]:
																				lowerCamelCase__		:   Optional[int]  				=					left_array[left_index]
																				left_index += 1
															else:
																				lowerCamelCase__		:   int  				=					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
															lowerCamelCase__		:   Any  				=					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
															lowerCamelCase__		:   str  				=					right_array[right_index]
															right_index += 1
															index += 1
					return arr


if __name__ == "__main__":
					import doctest

					doctest.testmod()







"""simple docstring"""







def   __lowerCAmelCase(		__UpperCAmelCase      ):






	"""simple docstring"""





	if len(__UpperCAmelCase      ) > 1:
		_lowercase			:     Dict      					=				len(__UpperCAmelCase      ) // 2  # Finds the middle of the array
		_lowercase			:     List[str]      					=				arr[
		    :middle_length
		]  # Creates an array of the elements in the first half.
		_lowercase			:     Optional[int]      					=				arr[
		    middle_length:
		]  # Creates an array of the elements in the second half.
		_lowercase			:     Optional[Any]      					=				len(__UpperCAmelCase      )
		_lowercase			:     Optional[int]      					=				len(__UpperCAmelCase      )
		merge(__UpperCAmelCase      )  # Starts sorting the left.
		merge(__UpperCAmelCase      )  # Starts sorting the right
		_lowercase			:     Dict      					=				0  # Left Counter
		_lowercase			:     List[str]      					=				0  # Right Counter
		_lowercase			:     Optional[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]:
				_lowercase			:     Optional[int]      					=				left_array[left_index]
				left_index += 1
			else:
				_lowercase			:     int      					=				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
			_lowercase			:     Any      					=				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
			_lowercase			:     str      					=				right_array[right_index]
			right_index += 1
			index += 1
	return arr


if __name__ == "__main__":
						import doctest

						doctest.testmod()



