|
Sep. 26th, 2018|04:46 pm |
Стек, если я правильно понимаю, там нужен только на три run'а - перед тем, как сунуть туда следующий, какие-то два объединяются. Это, действительно, байты.
А вот для того, чтобы смержить два массива, может понадобиться дополнительная память размером с один из них. И если так сложится, что на последнем этапе будет два run'а по гигабайту каждый - то придется где-то брать гигабайт дополнительной памяти.
Частично упорядоченные массивы - это какой-то фантастический случай, честно говоря. Я только один реальный сценарий этого вижу: нам надо поддерживать отсортированный массив каких-то величин, а эти величины продолжают откуда-то поступать. Мы дописываем вновь полученные данные в конец массива, и запускаем тимсорт. Вот тогда заебись будет, любой другой алгоритм соснет.
Только вот умный человек так делать не будет, он отсортирует новые данные (не важно, чем - их все равно мало), а затем смержит два отсортированных массива (причем поскольку в первом массиве уже должно быть место под дополнительные элементы, то нам даже память выделять как бы и не понадобится).
Так что на мой вкус тимсорт - это что-то для питонобыла ебаного, которое сортирует одно и то же по пятьсот раз подряд, потому что не понимают вообще нихуя, Кнута не читали, пидоры сраные, а лезут программировать. Дай им квиксорт - они и его поломают, и хуй себе изрежут. |
|