Я изучаю некоторые алгоритмы сортировки и время их выполнения. Я реализовал некоторые алгоритмы в Python и измеряю, сколько времени они занимают, чтобы отсортировать некоторые массивы.
Я обнаружил, что Python изначально реализует Timsort в качестве алгоритма сортировки списков.
Однако я хотел сравнить нативный Timsort с реализацией, которую я нашел на GitHub ( эта ).
Как это возможно, что собственная реализация занимает 0,000630140304565 секунд, чтобы отсортировать массив из 51200 элементов, в то время как реализация, которую я связал ранее, занимает 40,7546050549 секунд, чтобы отсортировать тот же массив?
[EDIT]
Чтобы получить время, я использую "time.time ()" до и после выполнения алгоритма сортировки, а затем просто делаю разницу.
Я ожидал, что нативная реализация будет быстрее, но не так сильно. Дело в том, что я реализовал и другие алгоритмы сортировки в Python, и, например, Merge-Sort занимает 0,148133039474 секунды для сортировки того же массива.
Я не ожидал такой большой разницы между Merge-Sort и Python-реализацией Timsort.
[EDIT2]
Так что проблема в том, что обнаруженная мною реализация неэффективна и на самом деле не Timsort.
Извините, ребята, я только что обнаружил, что Timsort был тэтой (nlgn), и я верил, что это правильная реализация. Теперь проблема в следующем: существует ли эффективная реализация Timsort на Python?