Внешняя сортировка за линейное время

> Ну две под последовательности сливают конечно за линейное, но там ведь последовательностей большое количество

ну да, там логарифм количества последовательностей домножается. А как без этого — если последовательностей столько же сколько элементов, то есть в каждой последовательности один элемент, то задача превращается в обычную сортировку, ты ее тоже хочешь линейно сделать?

Если рассуждать логически - то да, буфер фиксированный, а следовательно количество кусков будет линейно зависить от количества элементов.

Пришло озарение! Вобще-то в условии указано ограничение - сортируются числа unsinged short. Получается что можно использовать сортировку подсчетом на всем файле, а не только на кусках, ведь память всеравно будет фиксированаая, и не такая уж и большая.

Спасибо!

radix sort?

nlog(n)

если используется сравнение элементов и не используется дополнительная память, если потратить больше памяти, то можно сделать быстрее

Хм, подобное было у Яндекса при отсеве на собеседование:

Задачка

Для сортировки файлов, которые не помещаются в оперативную память применяют внешнюю сортировку. При этом наиболее долгими являются операции обращения к жесткому диску. Разработайте алгоритм внешней сортировки, у которого количество операций чтения O(N log N), а количество операций записи O(N).

и чем же оно подобное? оба про сортировку?:)