





'''simple docstring'''



def  lowercase__(		_UpperCamelCase  : list[int]				)->   list[int]:






					"""simple docstring"""

					if len(_UpperCamelCase				) > 1:
										_UpperCamelCase											=   len(_UpperCamelCase				) // 2  # Finds the middle of the array
										_UpperCamelCase											=   arr[
										    :middle_length
										]  # Creates an array of the elements in the first half.
										_UpperCamelCase											=   arr[
										    middle_length:
										]  # Creates an array of the elements in the second half.
										_UpperCamelCase											=   len(_UpperCamelCase				)
										_UpperCamelCase											=   len(_UpperCamelCase				)
										merge(_UpperCamelCase				)  # Starts sorting the left.
										merge(_UpperCamelCase				)  # Starts sorting the right
										_UpperCamelCase											=   0  # Left Counter
										_UpperCamelCase											=   0  # Right Counter
										_UpperCamelCase											=   0  # Position Counter
										while (
										    left_index < left_size and right_index < right_size
										):  # Runs until the lowers size of the left and right are sorted.
															if left_array[left_index] < right_array[right_index]:
																				_UpperCamelCase											=   left_array[left_index]
																				left_index += 1
															else:
																				_UpperCamelCase											=   right_array[right_index]
																				right_index += 1
															index += 1
										while (
										    left_index < left_size
										):  # Adds the left over elements in the left half of the array
															_UpperCamelCase											=   left_array[left_index]
															left_index += 1
															index += 1
										while (
										    right_index < right_size
										):  # Adds the left over elements in the right half of the array
															_UpperCamelCase											=   right_array[right_index]
															right_index += 1
															index += 1
					return arr


if __name__ == "__main__":
			import doctest

			doctest.testmod()










'''simple docstring'''



from __future__ import annotations



def  lowercase__(		_UpperCamelCase  : list[list[int]] ,   _UpperCamelCase  : int ,   _UpperCamelCase  : int ,   _UpperCamelCase  : int | float				)->   None:






					"""simple docstring"""

					_UpperCamelCase				,	_UpperCamelCase											=   m - 1, 0
					while i >= 0 and j < n:
										if key == mat[i][j]:
															print(f"Key {key} found at row- {i + 1} column- {j + 1}"				)
															return
										if key < mat[i][j]:
															i -= 1
										else:
															j += 1
					print(f"Key {key} not found"				)



def  lowercase__(		)->   None:






					"""simple docstring"""

					_UpperCamelCase											=   [[2, 5, 7], [4, 8, 13], [9, 11, 15], [12, 17, 20]]
					_UpperCamelCase											=   int(input("Enter the element to be searched:"				)				)
					print(_UpperCamelCase				)
					search_in_a_sorted_matrix(_UpperCamelCase ,   len(_UpperCamelCase				) ,   len(mat[0]				) ,   _UpperCamelCase				)


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			main()



