如何使用合併排序對外部排序中的運行進行排序

Question

我想實現（在C中）使用合併排序爲高校分配的數據庫的外部排序算法。可用內存爲buffSize塊。我發現這個鏈接非常有用：

http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html

但我的問題是關於這一行的僞代碼，在算法的一個階段：

sort array a using an in-memory algorithm like quicksort

如果我不去有權使用除我的buffSize空間以外的任何內存，因此我無法分配鏈接的a陣列，如何對包含在這些塊中的記錄進行排序（然後將它們存儲在臨時運行文件中），使用內存中的分類程序（例如快速排序）。在這種情況下，我的記錄不會是連續的數組，而是位於非連續的內存塊中，我不能直接應用qsort。任何提示？

Answer 1

用於外部排序的一般方法是：

1. 閱讀儘可能多的數據將裝配到一個陣列中的存儲器。
2. 對其進行排序。
3. 寫出一個臨時文件（記錄名稱和大小以及最大記錄等）。
4. 回到第1步，直到數據結束。
5. 爲寫入的文件設置合併樹，以便儘可能少地合併。
6. 從每個第一個（僅限？）合併階段輸入文件中讀取一行。
7. 將最小的（用於升序排序）寫入下一個臨時文件（或最終文件）。
8. 獲取新記錄以替換剛寫入的記錄。
9. 回到第7步，直到沒有更多數據要讀取。
10. 返回步驟6繼續合併，直到完成。

你沒有詳細的意思的內存buffSize塊，但有一個陣列a，可以在內存中進行排序。所以，你將數據讀入數組中。您使用快速排序對數組進行排序。然後你將數組寫入磁盤。重複閱讀，排序，寫作，直到沒有更多的輸入數據。然後做合併...