D
Нет, n и m
Size: a a a
2020 July 12
D
Точнее необязательно, в массивах целые числа
EZ
Можно ли смерджить два массива, один отсортированный, второй нет, так, чтобы результирующий массив был отсортирован и алгоритм работал быстрее O(mlogm)+O(n+m)?
Для произвольных n и m нет
EZ
Потому что тогда ты просто сортируешь быстрее mlogm
D
Пытался придумать с бинпоиском что-то, но не могу порядок поддерживать
EZ
Ну точнее быстрее чем "посортировать несортированный и смержить" нельзя
D
А с карманной сортировкой тяжело будет?
EZ
А с карманной сортировкой тяжело будет?
Странный вопрос, что значит тяжело?
D
На сколько я помню там данные должны быть равномерно распределены
D
Если там правильно научиться раскидывать по карманам, нужны эвристики какие-то
D
Или я неправ?
D
Просто карманная линейна
CD
я очень сильно сомневаюсь в словосочетании "линейная сортировка" применительно к сортировкам, которые называют линейными
CD
мне кажется, что это какое-то злоупотребление арифметическими поправками
D
Окей, сублинейная)
CD
в общем, Евгений совершенно верно указывает, что задача в точности сортировка несортированной части
D
Окей, тоже так думаю, другу на собесе дали задачу и попросили быстрее сделать)
CD
ну корзиночки "работают" и без равномерности
CD
так что "O(n + m)" у нас будет для чисел
CD
4 раунда по 2^16 корзин и никаких проблем