In computer science, merge sort (also normally spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. A detailed description and analysis of bottom-up mergesort looked in a report by Goldstine and von Neumann as early as 1948.
Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. divide the unsorted list into N sublists, each containing one component (a list of one component is considered sorted).
""" This is a pure Python implementation of the merge sort algorithm For doctests run following command: python -m doctest -v merge_sort.py or python3 -m doctest -v merge_sort.py For manual testing run: python merge_sort.py """ def merge_sort(collection): """Pure implementation of the merge sort algorithm in Python :param collection: some mutable ordered collection with heterogeneous comparable items inside :return: the same collection ordered by ascending Examples: >>> merge_sort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5] >>> merge_sort()  >>> merge_sort([-2, -5, -45]) [-45, -5, -2] """ def merge(left, right): """merge left and right :param left: left collection :param right: right collection :return: merge result """ result =  while left and right: result.append((left if left <= right else right).pop(0)) return result + left + right if len(collection) <= 1: return collection mid = len(collection) // 2 return merge(merge_sort(collection[:mid]), merge_sort(collection[mid:])) if __name__ == "__main__": user_input = input("Enter numbers separated by a comma:\n").strip() unsorted = [int(item) for item in user_input.split(",")] print(*merge_sort(unsorted), sep=",")