Twitter | Search | |
Rustem Mustafin 23 May 19
Кто-то представляет, можно ли доказать, что N сортированных списков нельзя смержить в один сортированный список за линейное время?
Reply Retweet Like
Dmitry Kalyanov
Например, через reductio ad absurdum: если возьмем N списков, каждый из которых содержит ровно один элемента и смержим их за линейное время, то получим линейный алгоритм сортировки сравнением, что невозможно.
Reply Retweet Like More
Rustem Mustafin 4 Jun 19
Replying to @dmitry_vk
В продолжении: я думаю над подходом, когда все числа из списков кидаются в массив + фиксируется информация о границах (по индексам и значениям) отсортированных кусков массива. Вопрос: как бы использовать эту доп. инфу, чтоб этот массив быстрее отсортировать (comparison-based)?
Reply Retweet Like
Dmitry Kalyanov 11 Jun 19
Replying to @Rulikkk
Навскидку: можно взять идею из quicksort; если есть разбиение на непересекающиеся фрагменты, то их не нужно сливать.
Reply Retweet Like
Rustem Mustafin 29 May 19
Replying to @dmitry_vk
Ждал твоего ответа!
Reply Retweet Like