'''simple docstring'''




from __future__ import annotations






def 				snake_case__							(			_A:					list      ,   _A:					int      ,   _A:					int      ,   _A:					int )    ->	list:

		'''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__							(			_A:					list )    ->	list:

		'''simple docstring'''


		if len(_A ) <= 1:
				return input_list
		lowerCAmelCase   					=  list(_A )

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

		return input_list


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





'''simple docstring'''




def 				snake_case__							(			_A:					str )    ->	list[int]:

		'''simple docstring'''


		lowerCAmelCase   					=  [0 for i in range(len(_A ) )]

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

		for i in range(1      ,   len(_A ) ):
				# 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(_A      ,   _A      ,   _A ):
						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__							(			_A:					int      ,   _A:					list[int]      ,   _A:					str )    ->	bool:

		'''simple docstring'''


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






def 				snake_case__							(			_A:					str      ,   _A:					str )    ->	int:

		'''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(_A ):
						answer += 1

		return answer


if __name__ == "__main__":
						import doctest

						doctest.testmod()




