Estou tendo alguns problemas para entender esse comportamento. Estou medindo o tempo de execução com o timeit-module e obtenho os seguintes resultados para 10000 ciclos:

Merge: 1.22722930395Bubble: 0.810706578175Selecione: 0.469924766812

Este é o meu código para o 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

Editar

Alterei as operações da lista para usar ponteiros e meus testes agora funcionam com uma lista de 1000 números aleatórios de 0 a 1000. (btw: mudei para apenas 10 ciclos aqui)

resultado

Merge: 0.0574434420723Bubble: 1.74780097558Selecione: 0.362952293025

Esta é minha definição de mesclagem reescrita:

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

parece funcionar muito bem agora