
from __future__ import annotations

from collections.abc import Iterable, Iterator
from typing import Any, Generic, TypeVar

_UpperCamelCase:					str     =TypeVar('T', bound=bool)





class 						__lowercase(     Generic[T]   ):


       """simple docstring"""







       def __init__(     self					:			Optional[Any]  ,      _lowerCAmelCase					:			T       )					->   None:
         _lowerCAmelCase						=		value
         _lowerCAmelCase						=		None
         _lowerCAmelCase						=		None



       @property
       def SCREAMING_SNAKE_CASE_				(     self					:			Any       )					->   T:
         return self._value






       @staticmethod
       def SCREAMING_SNAKE_CASE_				(     _lowerCAmelCase					:			SkewNode[T] | None  ,      _lowerCAmelCase					:			SkewNode[T] | None       )					->   SkewNode[T] | None:
         if not roota:
           return roota

         if not roota:
           return roota

         if roota.value > roota.value:
           _lowerCAmelCase	,       _lowerCAmelCase						=		roota, roota

         _lowerCAmelCase						=		roota
         _lowerCAmelCase						=		roota.right
         _lowerCAmelCase						=		roota.left
         _lowerCAmelCase						=		SkewNode.merge(_lowerCAmelCase  ,      _lowerCAmelCase       )

         return result





class 						__lowercase(     Generic[T]   ):


       """simple docstring"""







       def __init__(     self					:			int  ,      _lowerCAmelCase					:			Iterable[T] | None = ()       )					->   None:
         _lowerCAmelCase						=		None
         if data:
           for item in data:
             self.insert(_lowerCAmelCase       )



       def __bool__(     self					:			Union[str, Any]       )					->   bool:
         return self._root is not None



       def __iter__(     self					:			int       )					->   Iterator[T]:
         _lowerCAmelCase						=		[]
         while self:
           result.append(self.pop()       )

         # Pushing items back to the heap not to clear it.
         for item in result:
           self.insert(_lowerCAmelCase       )

         return iter(_lowerCAmelCase       )



       def SCREAMING_SNAKE_CASE_				(     self					:			Optional[int]  ,      _lowerCAmelCase					:			T       )					->   None:
         _lowerCAmelCase						=		SkewNode.merge(self._root  ,      SkewNode(_lowerCAmelCase       )       )



       def SCREAMING_SNAKE_CASE_				(     self					:			List[str]       )					->   T | None:
         _lowerCAmelCase						=		self.top()
         _lowerCAmelCase						=		(
             SkewNode.merge(self._root.left  ,      self._root.right       ) if self._root else None
         )

         return result



       def SCREAMING_SNAKE_CASE_				(     self					:			Tuple       )					->   T:
         if not self._root:
           raise IndexError('Can\'t get top element for the empty heap.'       )
         return self._root.value






       def SCREAMING_SNAKE_CASE_				(     self					:			int       )					->   None:
         _lowerCAmelCase						=		None


if __name__ == "__main__":
       import doctest

       doctest.testmod()


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()
