



def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					if start == end:
										return start if lst[start] > item else start + 1
					if start > end:
										return start

					lowercase						   =       (start + end) // 2
					if lst[mid] < item:
										return binary_search(_UpperCAmelCase       ,			_UpperCAmelCase       ,			mid + 1       ,			_UpperCAmelCase				)
					elif lst[mid] > item:
										return binary_search(_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase       ,			mid - 1				)
					else:
										return mid





def 		__snake_case						(    _UpperCAmelCase				):
					"""simple docstring"""






					lowercase						   =       len(_UpperCAmelCase				)

					for index in range(1       ,			_UpperCAmelCase				):
										lowercase						   =       lst[index]
										lowercase						   =       binary_search(_UpperCAmelCase       ,			_UpperCAmelCase       ,			0       ,			index - 1				)
										lowercase						   =       lst[:pos] + [value] + lst[pos:index] + lst[index + 1 :]

					return lst





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					if not left:
										return right

					if not right:
										return left

					if left[0] < right[0]:
										return [left[0], *merge(left[1:]       ,			_UpperCAmelCase				)]

					return [right[0], *merge(_UpperCAmelCase       ,			right[1:]				)]





def 		__snake_case						(    _UpperCAmelCase				):
					"""simple docstring"""






					lowercase						   =       len(_UpperCAmelCase				)
					lowercase   ,      lowercase						   =       [], []
					lowercase						   =       [lst[0]]
					lowercase						   =       []
					lowercase						   =       1
					while i < length:
										if lst[i] < lst[i - 1]:
															runs.append(_UpperCAmelCase				)
															lowercase						   =       [lst[i]]
										else:
															new_run.append(lst[i]				)
										i += 1
					runs.append(_UpperCAmelCase				)

					for run in runs:
										sorted_runs.append(insertion_sort(_UpperCAmelCase				)				)
					for run in sorted_runs:
										lowercase						   =       merge(_UpperCAmelCase       ,			_UpperCAmelCase				)

					return sorted_array





def 		__snake_case						(    ):
					"""simple docstring"""






					lowercase						   =       [5, 9, 10, 3, -4, 5, 1_78, 92, 46, -18, 0, 7]
					lowercase						   =       tim_sort(_UpperCAmelCase				)
					print(_UpperCAmelCase				)


if __name__ == "__main__":
		main()











def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					if right <= left:
										return
					lowercase						   =       lowercase						   =       left
					lowercase						   =       right
					lowercase						   =       sorting[left]
					while i <= b:
										if sorting[i] < pivot:
															lowercase   ,      lowercase						   =       sorting[i], sorting[a]
															a += 1
															i += 1
										elif sorting[i] > pivot:
															lowercase   ,      lowercase						   =       sorting[i], sorting[b]
															b -= 1
										else:
															i += 1
					quick_sort_apartition(_UpperCAmelCase       ,			_UpperCAmelCase       ,			a - 1				)
					quick_sort_apartition(_UpperCAmelCase       ,			b + 1       ,			_UpperCAmelCase				)





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					if left < right:
										lowercase						   =       lomuto_partition(_UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				)
										quick_sort_lomuto_partition(_UpperCAmelCase       ,			_UpperCAmelCase       ,			pivot_index - 1				)
										quick_sort_lomuto_partition(_UpperCAmelCase       ,			pivot_index + 1       ,			_UpperCAmelCase				)





def 		__snake_case						(    _UpperCAmelCase       ,			_UpperCAmelCase       ,			_UpperCAmelCase				):
					"""simple docstring"""






					lowercase						   =       sorting[right]
					lowercase						   =       left
					for i in range(_UpperCAmelCase       ,			_UpperCAmelCase				):
										if sorting[i] < pivot:
															lowercase   ,      lowercase						   =       sorting[i], sorting[store_index]
															store_index += 1
					lowercase   ,      lowercase						   =       sorting[store_index], sorting[right]
					return store_index





def 		__snake_case						(    _UpperCAmelCase				):
					"""simple docstring"""






					if len(_UpperCAmelCase				) <= 1:
										return sorting
					return (
					    three_way_radix_quicksort([i for i in sorting if i < sorting[0]]				)
					    + [i for i in sorting if i == sorting[0]]
					    + three_way_radix_quicksort([i for i in sorting if i > sorting[0]]				)
					)


if __name__ == "__main__":
		import doctest

		doctest.testmod(verbose=True)

		__magic_name__       =     input('''Enter numbers separated by a comma:\n''').strip()
		__magic_name__       =     [int(item) for item in user_input.split(''',''')]
		quick_sort_apartition(unsorted, 0, len(unsorted) - 1)
		print(unsorted)






