Может ли такое быть, что менее продвинутый алгоритм сортировки выполняется быстрее?

Question

[AkunaGPT]

Почему сортировка Шелла в C++ по моим замерам работает быстрее по времени, чем слияния для сортировки массива из 10 млн элементов? Вроде бы уже на таком размере разница должна быть видна. Я проверял время через <chrono> и <ctime>, а также на онлайн-сервисах, где показано за сколько выполнилась программа. Реализации брал стандартные, буквально с первых страниц в поисковике.
В Python такого не происходит, всё как ожидается. Почему так? Или я что-то не так делаю / понимаю?

Comments

[fenrir]

А вашу реализацию нам угадывать?

[AkunaGPT]

fenrir, далеко ходить не надо, например, то, что выдает чат гтп

[Aetae]

AkunaGPT,
1. ChatGPT не доступен в РФ по причине нацизама хозяев.
2. Даже если это обойти - никто не будет читать твою переписку.

Обозначь конкретные куски кода с конкретным описанием или иди в бан.

[aleks-th]

AkunaGPT, ну тогда у чат гпт и спрашивай.
Зачем тебе вопросы людям задавать.

без твоего кода "ответ 32" - будет тоже абсолютно правильным и таким же бесполезным

Answer 1

[VoidVolker]

Да, конечно может. Почему нет-то? "Продвинутость" алгоритма - понятие довольно абстрактное. Обычно алгоритмы сортировки характеризуются несколькими параметрами: сложность сортировки, скорость, потребляемая память.

Answer 2

[Wataru]

Разные алгоритмы имеют разные лучшие и худшие случаи. Например, на почти отсортированном массиве сортировка шелла отработает весьма быстро - сильно быстрее сортировки случайного массива. Сортировка слиянием же выполнит примерно одинаковое количество операций для любого массива. Так что можно подобрать даже весьма большой тест, на котором сортировка Шелла обгонит сортировку слиянием.