Существуют ли какие-либо алгоритмы для сортировки данных из последовательного ввода с использованием буфера, который меньше длины данных?
Например, у меня есть 100 байт последовательных данных, которые можно прочитать только один раз, и 40 байт буфера. И мне нужно распечатать отсортированные байты.
Мне нужно это в Javascript, но любые общие идеи приветствуются.
Такая сортировка невозможна за один проход.
Используя ваш пример: предположим, вы заполнили свой 40-байтовый буфер, поэтому вам нужно начать распечатывать байты, чтобы освободить место для следующего. Чтобы распечатать отсортированные данные, вы должны сначала напечатать наименьший байт. Однако, если наименьший байт не был прочитан, вы еще не можете его распечатать!
Ближе всего к вашему вопросу подходят алгоритмы внешней сортировки, которые выполняют несколько проходов для сортировки данные, которые не помещаются в память. То есть, если у вас есть периферийные устройства, которые могут хранить выходные данные прохода обработки, вы можете сортировать данные, превышающие размер вашей памяти, за проходы O(log(N/M)), где N — размер проблемы, а M — размер вашей памяти.
Классическим периферийным устройством хранения данных для внешней сортировки является ленточный накопитель; однако те же самые алгоритмы работают для дисководов (любого типа). Кроме того, по мере увеличения глубины иерархии кэша принципы внешней сортировки становятся более актуальными даже для сортировки в памяти — попробуйте взглянуть на не обращающие внимания на кеш.
