
from typing import Any





class 						__lowercase:


       """simple docstring"""







       def __init__(     self					:			str       )					->   List[str]:
         _lowerCAmelCase						=		[]
         _lowerCAmelCase						=		0



       def __str__(     self					:			Union[str, Any]       )					->   Any:
         _lowerCAmelCase						=		'<' + str(self.stack       )[1:-1] + '>'
         return printed



       def SCREAMING_SNAKE_CASE_				(     self					:			Optional[int]  ,      _lowerCAmelCase					:			Any       )					->   None:
         self.stack.append(_lowerCAmelCase       )
         _lowerCAmelCase						=		self.length + 1



       def SCREAMING_SNAKE_CASE_				(     self					:			Dict       )					->   Any:
         self.rotate(1       )
         _lowerCAmelCase						=		self.stack[self.length - 1]
         _lowerCAmelCase						=		self.stack[:-1]
         self.rotate(self.length - 1       )
         _lowerCAmelCase						=		self.length - 1
         return dequeued



       def SCREAMING_SNAKE_CASE_				(     self					:			Tuple  ,      _lowerCAmelCase					:			int       )					->   None:
         for _ in range(_lowerCAmelCase       ):
           _lowerCAmelCase						=		self.stack[0]
           _lowerCAmelCase						=		self.stack[1:]
           self.put(_lowerCAmelCase       )
           _lowerCAmelCase						=		self.length - 1



       def SCREAMING_SNAKE_CASE_				(     self					:			Dict       )					->   Any:
         _lowerCAmelCase						=		self.get()
         self.put(_lowerCAmelCase       )
         self.rotate(self.length - 1       )
         return front



       def SCREAMING_SNAKE_CASE_				(     self					:			List[Any]       )					->   int:
         return self.length


from __future__ import annotations



def 	_a  (					__SCREAMING_SNAKE_CASE					:  list		,				__SCREAMING_SNAKE_CASE					:  list    ):






  """simple docstring"""




  _lowerCAmelCase						=		[None] * (len(__SCREAMING_SNAKE_CASE    ) + len(__SCREAMING_SNAKE_CASE    ))

  _lowerCAmelCase						=		0  # pointer to current index for left Half
  _lowerCAmelCase						=		0  # pointer to current index for the right Half
  _lowerCAmelCase						=		0  # pointer to current index for the sorted array Half

  while pointera < len(__SCREAMING_SNAKE_CASE    ) and pointera < len(__SCREAMING_SNAKE_CASE    ):
    if left_half[pointera] < right_half[pointera]:
      _lowerCAmelCase						=		left_half[pointera]
      pointera += 1
      index += 1
    else:
      _lowerCAmelCase						=		right_half[pointera]
      pointera += 1
      index += 1
  while pointera < len(__SCREAMING_SNAKE_CASE    ):
    _lowerCAmelCase						=		left_half[pointera]
    pointera += 1
    index += 1

  while pointera < len(__SCREAMING_SNAKE_CASE    ):
    _lowerCAmelCase						=		right_half[pointera]
    pointera += 1
    index += 1

  return sorted_array



def 	_a  (					__SCREAMING_SNAKE_CASE					:  list    ):






  """simple docstring"""




  if len(__SCREAMING_SNAKE_CASE    ) <= 1:
    return array
  # the actual formula to calculate the middle element = left + (right - left) // 2
  # this avoids integer overflow in case of large N
  _lowerCAmelCase						=		0 + (len(__SCREAMING_SNAKE_CASE    ) - 0) // 2

  # Split the array into halves till the array length becomes equal to One
  # merge the arrays of single length returned by mergeSort function and
  # pass them into the merge arrays function which merges the array
  _lowerCAmelCase						=		array[:middle]
  _lowerCAmelCase						=		array[middle:]

  return merge(merge_sort(__SCREAMING_SNAKE_CASE    )		,				merge_sort(__SCREAMING_SNAKE_CASE    )    )


if __name__ == "__main__":
       import doctest

       doctest.testmod()
