Может ли кто-нибудь указать мне хорошую ссылку на слияние внешней памяти? Я прочитал вики-страницу, но у меня возникли проблемы с ее точным пониманием. Анимация может помочь, но я не могу ее найти.
По сути, я знаю, что у вас есть определенное количество блоков на диске, и вы можете разместить определенное количество блоков в памяти. Допустим, у вас есть 32 блока на диске и 4 блока в памяти. На первом проходе вы читаете в память по 4 блока за раз, сортируете их в памяти и записываете обратно на диск. Итак, на данный момент у вас есть 8 отсортированных прогонов по 4 блока. Как работает слияние? Поскольку у меня есть 4 блока в памяти (предположим, что у меня есть еще один для вывода), я думаю, что должен иметь возможность объединить 4 из этих 8 прогонов за раз, а затем объединить следующие 4 прогона. И затем в последнем проходе я хочу объединить все это. Но разве вам не нужно каждый раз читать каждый блок с диска? Так как же это не становится решением n ^ 2?
