
"""simple docstring"""



from __future__ import annotations






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					list     ,  SCREAMING_SNAKE_CASE:					int     ,  SCREAMING_SNAKE_CASE:					int     ,  SCREAMING_SNAKE_CASE:					int						):






							"""simple docstring"""



							_lowerCAmelCase  	=			[]
							_lowerCAmelCase	,		_lowerCAmelCase  	=			input_list[low:mid], input_list[mid : high + 1]
							while left and right:
														result.append((left if left[0] <= right[0] else right).pop(0						)						)
							_lowerCAmelCase  	=			result + left + right
							return input_list






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					list						):






							"""simple docstring"""



							if len(SCREAMING_SNAKE_CASE						) <= 1:
														return input_list
							_lowerCAmelCase  	=			list(SCREAMING_SNAKE_CASE						)

							# iteration for two-way merging
							_lowerCAmelCase  	=			2
							while p <= len(SCREAMING_SNAKE_CASE						):
														# getting low, high and middle value for merge-sort of single list
														for i in range(0     ,  len(SCREAMING_SNAKE_CASE						)     ,  SCREAMING_SNAKE_CASE						):
																					_lowerCAmelCase  	=			i
																					_lowerCAmelCase  	=			i + p - 1
																					_lowerCAmelCase  	=			(low + high + 1) // 2
																					_lowerCAmelCase  	=			merge(SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE						)
														# final merge of last two parts
														if p * 2 >= len(SCREAMING_SNAKE_CASE						):
																					_lowerCAmelCase  	=			i
																					_lowerCAmelCase  	=			merge(SCREAMING_SNAKE_CASE     ,  0     ,  SCREAMING_SNAKE_CASE     ,  len(SCREAMING_SNAKE_CASE						) - 1						)
																					break
														p *= 2

							return input_list


if __name__ == "__main__":
			_snake_case          =						input('''Enter numbers separated by a comma:\n''').strip()
			if user_input == "":
						_snake_case          =						[]
			else:
						_snake_case          =						[int(item.strip()) for item in user_input.split(''',''')]
			print(iter_merge_sort(unsorted))








"""simple docstring"""



def 	__snake_case  (    SCREAMING_SNAKE_CASE:					str						):






							"""simple docstring"""



							_lowerCAmelCase  	=			[0 for i in range(len(SCREAMING_SNAKE_CASE						)						)]

							# initialize interval's left pointer and right pointer
							_lowerCAmelCase	,		_lowerCAmelCase  	=			0, 0

							for i in range(1     ,  len(SCREAMING_SNAKE_CASE						)						):
														# case when current index is inside the interval
														if i <= right_pointer:
																					_lowerCAmelCase  	=			min(right_pointer - i + 1     ,  z_result[i - left_pointer]						)
																					_lowerCAmelCase  	=			min_edge

														while go_next(SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE						):
																					z_result[i] += 1

														# if new index's result gives us more right interval,
														# we've to update left_pointer and right_pointer
														if i + z_result[i] - 1 > right_pointer:
																					_lowerCAmelCase	,		_lowerCAmelCase  	=			i, i + z_result[i] - 1

							return z_result






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					int     ,  SCREAMING_SNAKE_CASE:					list[int]     ,  SCREAMING_SNAKE_CASE:					str						):






							"""simple docstring"""



							return i + z_result[i] < len(SCREAMING_SNAKE_CASE						) and s[z_result[i]] == s[i + z_result[i]]






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					str     ,  SCREAMING_SNAKE_CASE:					str						):






							"""simple docstring"""



							_lowerCAmelCase  	=			0
							# concatenate 'pattern' and 'input_str' and call z_function
							# with concatenated string
							_lowerCAmelCase  	=			z_function(pattern + input_str						)

							for val in z_result:
														# if value is greater then length of the pattern string
														# that means this index is starting position of substring
														# which is equal to pattern string
														if val >= len(SCREAMING_SNAKE_CASE						):
																					answer += 1

							return answer


if __name__ == "__main__":
	import doctest

	doctest.testmod()






