Merge Sort

merge_sort(x)

Merge sort divides a list into two smaller lists, and recursively repeats the process on the two smaller lists till lists of single elements are obtained. These smaller lists are then combined to form a single sorted list of the original elements. It has an average time complexity of Θ(nlogn). Time complexity for the worst case is O(nlogn). Time complexity for the best case is Ω(nlogn).

merge_sort([4, 2, 3, 1, 0, 5]) [0, 1, 2, 3, 4, 5]

Parameters:

Name	Type	Description	Default
x	List	list to be sorted	required

Returns:

Type	Description
List	new sorted list

Source code in sorting_algorithms/merge_sort.py

def merge_sort(x: List) -> List:
    """Merge sort divides a list into two smaller lists, and recursively repeats the process on the two smaller lists
    till lists of single elements are obtained. These smaller lists are then combined to form a single sorted list of
    the original elements. It has an average time complexity of Θ(nlogn). Time complexity for the worst case is
    O(nlogn). Time complexity for the best case is Ω(nlogn).

    >>> merge_sort([4, 2, 3, 1, 0, 5])
    [0, 1, 2, 3, 4, 5]

    :param x: list to be sorted
    :return: new sorted list
    """
    length = len(x)

    if length <= 1:
        return x

    mid_idx = length // 2
    left = merge_sort(x[0:mid_idx])
    right = merge_sort(x[mid_idx:length])

    result = []
    while len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result.extend(left)
    result.extend(right)

    return result