'''simple docstring'''




from __future__ import annotations



def 						__snake_case (       lowerCAmelCase       :     list      ,  lowerCAmelCase       :     list			):
 __UpperCAmelCase         =					[None] * (len(lowerCAmelCase			) + len(lowerCAmelCase			))

 __UpperCAmelCase         =					0  # pointer to current index for left Half
 __UpperCAmelCase         =					0  # pointer to current index for the right Half
 __UpperCAmelCase         =					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]:
   __UpperCAmelCase         =					left_half[pointera]
   pointera += 1
   index += 1
  else:
   __UpperCAmelCase         =					right_half[pointera]
   pointera += 1
   index += 1
 while pointera < len(lowerCAmelCase			):
  __UpperCAmelCase         =					left_half[pointera]
  pointera += 1
  index += 1

 while pointera < len(lowerCAmelCase			):
  __UpperCAmelCase         =					right_half[pointera]
  pointera += 1
  index += 1

 return sorted_array



def 						__snake_case (       lowerCAmelCase       :     list			):
 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
 __UpperCAmelCase         =					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
 __UpperCAmelCase         =					array[:middle]
 __UpperCAmelCase         =					array[middle:]

 return merge(merge_sort(lowerCAmelCase			)      ,  merge_sort(lowerCAmelCase			)			)


if __name__ == "__main__":
     import doctest

     doctest.testmod()




'''simple docstring'''




def 						__snake_case (       lowerCAmelCase       :     list			):

 for insert_index, insert_value in enumerate(collection[1:]			):
  __UpperCAmelCase         =					insert_index
  while insert_index >= 0 and insert_value < collection[insert_index]:
   __UpperCAmelCase         =					collection[insert_index]
   insert_index -= 1
  if insert_index != temp_index:
   __UpperCAmelCase         =					insert_value
 return collection


if __name__ == "__main__":
     from doctest import testmod

     testmod()

     _UpperCamelCase				:		List[Any]       			=		input('Enter numbers separated by a comma:\n').strip()
     _UpperCamelCase				:		List[Any]       			=		[int(item) for item in user_input.split(',')]
     print(f"{insertion_sort(unsorted) = }")



