Неожиданная кривая производительности сортировки слиянием CPython

Я реализовал простой алгоритм сортировки слиянием на Python. Алгоритм и тестовый код приведены ниже:

import time
import random
import matplotlib.pyplot as plt
import math
from collections import deque

def sort(unsorted):
    if len(unsorted) <= 1:
        return unsorted
    to_merge = deque(deque([elem]) for elem in unsorted)
    while len(to_merge) > 1:
        left = to_merge.popleft()
        right = to_merge.popleft()
        to_merge.append(merge(left, right))
    return to_merge.pop()

def merge(left, right):
    result = deque()
    while left or right:
        if left and right:
            elem = left.popleft() if left[0] > right[0] else right.popleft()
        elif not left and right:
            elem = right.popleft()
        elif not right and left:
            elem = left.popleft()
        result.append(elem)
    return result

LOOP_COUNT = 100
START_N = 1
END_N = 1000

def test(fun, test_data):
    start = time.clock()
    for _ in xrange(LOOP_COUNT):
        fun(test_data)
    return  time.clock() - start

def run_test():
    timings, elem_nums = [], []
    test_data = random.sample(xrange(100000), END_N)
    for i in xrange(START_N, END_N):
        loop_test_data = test_data[:i]
        elapsed = test(sort, loop_test_data)
        timings.append(elapsed)
        elem_nums.append(len(loop_test_data))
        print "%f s --- %d elems" % (elapsed, len(loop_test_data))
    plt.plot(elem_nums, timings)
    plt.show()

run_test()

Насколько я вижу, все в порядке, и в результате я должен получить хорошую кривую N*logN. Но картина немного отличается:

Вещи, которые я пытался исследовать:

1. PyPy. Кривая в порядке.
2. Отключен сборщик мусора с помощью модуля gc. Неверное предположение. Вывод отладки показал, что он даже не запускается до конца теста.
3. Профилирование памяти с помощью meliae — ничего особенного или подозрительного. ` У меня была другая реализация (рекурсивная, использующая ту же функцию слияния), она действует аналогично. Чем больше полных тестовых циклов я создам - ​​тем больше "скачков" на кривой.

Так как же можно объяснить и, надеюсь, исправить такое поведение?

UPD: изменены списки на collections.deque

UPD2: добавлен полный тестовый код

UPD3: Я использую Python 2.7.1 на ОС Ubuntu 11.04, используя четырехъядерный ноутбук с частотой 2 Гц. Я пытался отключить большинство других процессов: количество спайков уменьшилось, но хотя бы один из них остался.