





'''simple docstring'''

from __future__ import annotations




def  _a     (				lowerCAmelCase_      ,   lowerCAmelCase_						):





      """simple docstring"""



      _snake_case		:						Optional[int]         =  [None] * (len(lowerCAmelCase_						) + len(lowerCAmelCase_						))

      _snake_case		:						Tuple         =  0  # pointer to current index for left Half
      _snake_case		:						str         =  0  # pointer to current index for the right Half
      _snake_case		:						Tuple         =  0  # pointer to current index for the sorted array Half

      while pointera < len(lowerCAmelCase_						) and pointera < len(lowerCAmelCase_						):
            if left_half[pointera] < right_half[pointera]:
                  _snake_case		:						Union[str, Any]         =  left_half[pointera]
                  pointera += 1
                  index += 1
            else:
                  _snake_case		:						Any         =  right_half[pointera]
                  pointera += 1
                  index += 1
      while pointera < len(lowerCAmelCase_						):
            _snake_case		:						str         =  left_half[pointera]
            pointera += 1
            index += 1

      while pointera < len(lowerCAmelCase_						):
            _snake_case		:						List[str]         =  right_half[pointera]
            pointera += 1
            index += 1

      return sorted_array




def  _a     (				lowerCAmelCase_						):





      """simple docstring"""



      if len(lowerCAmelCase_						) <= 1:
            return array
      # the actual formula to calculate the middle element = left + (right - left) // 2
      # this avoids integer overflow in case of large N
      _snake_case		:						Optional[Any]         =  0 + (len(lowerCAmelCase_						) - 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
      _snake_case		:						List[str]         =  array[:middle]
      _snake_case		:						Tuple         =  array[middle:]

      return merge(merge_sort(lowerCAmelCase_						)      ,   merge_sort(lowerCAmelCase_						)						)


if __name__ == "__main__":
   import doctest

   doctest.testmod()









'''simple docstring'''

from __future__ import annotations




def  _a     (				lowerCAmelCase_      ,   lowerCAmelCase_      ,   lowerCAmelCase_      ,   lowerCAmelCase_						):





      """simple docstring"""



      if counter == 0 or capacity == 0:
            return 0

      # If weight of the nth item is more than Knapsack of capacity,
      #   then this item cannot be included in the optimal solution,
      # else return the maximum of two cases:
      #   (1) nth item included
      #   (2) not included
      if weights[counter - 1] > capacity:
            return knapsack(lowerCAmelCase_      ,   lowerCAmelCase_      ,   lowerCAmelCase_      ,   counter - 1						)
      else:
            _snake_case		:						List[str]         =  capacity - weights[counter - 1]
            _snake_case		:						Tuple         =  values[counter - 1] + knapsack(
                lowerCAmelCase_      ,   lowerCAmelCase_      ,   lowerCAmelCase_      ,   counter - 1						)
            _snake_case		:						Any         =  knapsack(lowerCAmelCase_      ,   lowerCAmelCase_      ,   lowerCAmelCase_      ,   counter - 1						)
            return max(lowerCAmelCase_      ,   lowerCAmelCase_						)


if __name__ == "__main__":
   import doctest

   doctest.testmod()


