


from .hash_table import HashTable
from .number_theory.prime_numbers import is_prime, next_prime







class     __lowerCamelCase     (  snake_case_     ):


							"""simple docstring"""

							def __init__(  self						,       *UpperCAmelCase						,       **UpperCAmelCase  )     ->       Union[str, Any]:






								'''simple docstring'''






								super().__init__(*_lowerCAmelCase						,       **_lowerCAmelCase  )




							def 				A__      (  self						,       UpperCAmelCase						,       UpperCAmelCase  )     ->       Any:






								'''simple docstring'''






								lowercase_			 = (
								    next_prime(value % self.size_table  )
								    if not is_prime(value % self.size_table  )
								    else value % self.size_table
								)  # gt = bigger than
								return next_prime_gt - (data % next_prime_gt)




							def 				A__      (  self						,       UpperCAmelCase						,       UpperCAmelCase						,       UpperCAmelCase  )     ->       List[Any]:






								'''simple docstring'''






								return (increment * self.__hash_function_a(_lowerCAmelCase						,       _lowerCAmelCase  )) % self.size_table




							def 				A__      (  self						,       UpperCAmelCase						,       UpperCAmelCase=None  )     ->       str:






								'''simple docstring'''






								lowercase_			 = 1
								lowercase_			 = self.hash_function(_lowerCAmelCase  )

								while self.values[new_key] is not None and self.values[new_key] != key:
									lowercase_			 = (
									    self.__hash_double_function(_lowerCAmelCase						,       _lowerCAmelCase						,       _lowerCAmelCase  )
									    if self.balanced_factor() >= self.lim_charge
									    else None
									)
									if new_key is None:
										break
									else:
										i += 1

								return new_key



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