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