Почему сочетание сортировки вставок и быстрой сортировки приводит к худшим результатам?

Question

Я попытался установить срез, чтобы объединить быструю сортировку и сортировку вставкой, используя сортировку вставкой, когда n (количество данных для сортировки) меньше, чем отсечка. Однако я обнаружил, что метод не работает и даже хуже, чем раньше. Почему и как это улучшить?

Для сортировки 10e4 случайного целого числа быстрая сортировка с отсечкой (50) занимает 0,6 с, а метод без отсечки - всего 0,02 с.

Быстрая сортировка с отсечкой (50):

def quick_sort(line, l, r):
    if r - l > 50:
        pivot = find_median(line, l, r)
        i, j = l+1, r-2
        while True:
            while line[i] < pivot:
                i += 1
            while line[j] > pivot:
                j -= 1
            if i < j:
                line[i], line[j] = line[j], line[i]
                i += 1
                j -= 1
            else:
                break
        line[i], line[r-1] = line[r-1], line[i]
        quick_sort(line, l, i-1)
        quick_sort(line, i+1, r)
    else:
        insert_sort_index(line, l, r)


def find_median(line, l, r):
    center = (l + r) / 2
    if line[l] > line[r]:
        line[l], line[r] = line[r], line[l]
    if line[l] > line[center]:
        line[l], line[center] = line[center], line[l]
    if line[center] > line[r]:
        line[center], line[r] = line[r], line[center]
    line[center], line[r-1] = line[r-1], line[center]
    return line[r-1]


def insert_sort_index(line, l, r):
    if l < r:
        for idi in range(l+1, r+1):
            data = line[idi]
            for idj in range(idi+1)[::-1]:
                if idj >= l+1 and line[idj-1] > data:
                    line[idj] = line[idj-1]
                else:
                    break
            line[idj] = data

Метод без отсечки:

def quick_sort(line, l, r):
    if r - l > 1:
        pivot = find_median(line, l, r)
        i, j = l+1, r-2
        while True:
            while line[i] < pivot:
                i += 1
            while line[j] > pivot:
                j -= 1
            if i < j:
                line[i], line[j] = line[j], line[i]
                i += 1
                j -= 1
            else:
                break
        line[i], line[r-1] = line[r-1], line[i]
        quick_sort(line, l, i-1)
        quick_sort(line, i+1, r)
    else:
        if r == l + 1:
            if line[l] > line[r]:
                line[l], line[r] = line[r], line[l]

Answer 1

python3 реализует диапазон и другие функции в качестве итераторов / генераторов, так что, вероятно, в этом приложении это будет намного эффективнее, но функция диапазона python2 создает полный список в памяти.Вы несколько раз используете range insert_sort_index (и создаете другой список с помощью соединения [:: - 1]. Вы могли бы передать шаг в качестве аргумента для диапазона для этого).

Кажется, моя реализация на python2 оптимизируется дляЦиклы с диапазоном (0, x) затрудняли демонстрацию проблемы, но не тогда, когда (l, r) находится в более широком списке, как в случае с этим отсечением быстрой сортировки.

Я измерял прибл.двойная скорость сортировки вставки при работе с диапазоном большего списка, используя цикл while для idi, idj вместо range ().