я проблемы с пониманием этого поведения. Я измеряю время выполнения с помощью модуля timeit и получаю следующие результаты для10000 циклы:

Слияние:+1,22722930395Bubble: 0.810706578175Выберите: 0.469924766812

Это мой код для MergeSort:

def mergeSort(array):
    if len(array) <= 1:
        return array
    else:
        left = array[:len(array)/2]
        right = array[len(array)/2:]
        return merge(mergeSort(left),mergeSort(right))

def merge(array1,array2):
    merged_array=[]
    while len(array1) > 0 or len(array2) > 0:

        if array2 and not array1:
            merged_array.append(array2.pop(0))

        elif (array1 and not array2) or array1[0] < array2[0]:
            merged_array.append(array1.pop(0))

        else:
            merged_array.append(array2.pop(0))
    return merged_array

Редактировать:

Я изменил операции со списком, чтобы использовать указатели, и теперь мои тесты работают со списком из 1000 случайных чисел от 0 до 1000. (кстати: я изменил только 10 циклов здесь)

результат:

Слияние:+0,0574434420723Пузырь: 1.74780097558Выберите: 0.362952293025

Это мое переписанное определение слияния:

def merge(array1, array2):
    merged_array = []
    pointer1, pointer2 = 0, 0
    while pointer1 < len(array1) and pointer2 < len(array2):
        if array1[pointer1] < array2[pointer2]:
            merged_array.append(array1[pointer1])
            pointer1 += 1
        else:
            merged_array.append(array2[pointer2])
            pointer2 += 1
    while pointer1 < len(array1):
        merged_array.append(array1[pointer1])
        pointer1 += 1

    while pointer2 < len(array2):
        merged_array.append(array2[pointer2])
        pointer2 += 1

    return merged_array

похоже, сейчас работает очень хорошо :)