def merge_sort(array):
    """
    Merge Sort
    Complexity: O(NlogN)
    """

    if len(array) > 1:
        mid = len(array) // 2
        left = array[:mid]
        right = array[mid:]
        left = merge_sort(left)
        right = merge_sort(right)
        array = []

        # This is a queue implementation. We can also use
        # a deque but slicing it needs the itertools slice
        # function which I didn't want to use. More on that
        # in the stacks and queues chapter.
        l1 = l2 = 0
        while len(left) > l1 and len(right) > l2:
            if left[l1] < right[l2]:
                array.append(left[l1])
                l1 += 1
            else:
                array.append(right[l2])
                l2 += 1

        while len(left) > l1:
            array.append(left[l1])
            l1 += 1

        while len(right) > l2:
            array.append(right[l2])
            l2 += 1

    return array