merge sort Algorithm

Merge sort is a highly efficient, stable, and comparison-based sorting algorithm that employs the divide and conquer strategy. It works by recursively dividing the unsorted array or list into two equal halves, sorting each half individually, and then merging them back together into a single sorted array. This process of dividing, sorting, and merging continues until the entire array is sorted. The primary advantage of merge sort is its ability to handle large data sets with a time complexity of O(n log n), making it significantly faster than many other sorting algorithms, such as bubble sort and insertion sort. The merge sort algorithm begins by dividing the input array into two halves. Each half is then sorted recursively using the same merge sort algorithm. Once both halves are sorted, they are combined or merged back together in a manner that maintains their sorted order. This merging process involves iterating through each element in the two halves and comparing them, selecting the smaller element and placing it in the sorted array. This comparison and selection process continues until all elements from both halves have been placed in the sorted array. The merge step is a crucial aspect of the merge sort algorithm, as it ensures that the combined array remains sorted. The process of dividing, sorting, and merging is repeated until the entire array is sorted, resulting in a highly efficient and reliable sorting algorithm that is particularly well-suited for handling large data sets.
"""
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[0] <= right[0] 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=",")

LANGUAGE:

DARK MODE: