


from hashlib import mda, shaaaa

SCREAMING_SNAKE_CASE__       			=				(shaaaa, mda)







class     __lowerCamelCase     :


							"""simple docstring"""

							def __init__(  self						,       UpperCAmelCase = 8  )     ->       None:






								'''simple docstring'''






								lowercase_			 = 0b0
								lowercase_			 = size




							def 				A__      (  self						,       UpperCAmelCase  )     ->       None:






								'''simple docstring'''






								lowercase_			 = self.hash_(_lowerCAmelCase  )
								self.bitarray |= h




							def 				A__      (  self						,       UpperCAmelCase  )     ->       bool:






								'''simple docstring'''






								lowercase_			 = self.hash_(_lowerCAmelCase  )
								return (h & self.bitarray) == h




							def __contains__(  self						,       UpperCAmelCase  )     ->       bool:






								'''simple docstring'''






								return self.exists(_lowerCAmelCase  )




							def 				A__      (  self						,       UpperCAmelCase  )     ->       str:






								'''simple docstring'''






								lowercase_			 = bin(_lowerCAmelCase  )[2:]
								return res.zfill(self.size  )




							@property
							def 				A__      (  self  )     ->       str:






								'''simple docstring'''






								return self.format_bin(self.bitarray  )




							def 				A__      (  self						,       UpperCAmelCase  )     ->       int:






								'''simple docstring'''






								lowercase_			 = 0b0
								for func in HASH_FUNCTIONS:
									lowercase_			 = (
									    int.from_bytes(func(value.encode()  ).digest()						,       "little"  ) % self.size
									)
									res |= 2**position
								return res




							def 				A__      (  self						,       UpperCAmelCase  )     ->       str:






								'''simple docstring'''






								return self.format_bin(self.hash_(_lowerCAmelCase  )  )




							@property
							def 				A__      (  self  )     ->       float:






								'''simple docstring'''






								lowercase_			 = bin(self.bitarray  ).count("1"  )
								return (n_ones / self.size) ** len(_lowerCAmelCase  )



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