磁帶檔案排序

排序過程

磁帶檔案的排序過程類似於磁碟檔案的排序過程，步驟如下：

（1）把檔案的記錄分段輸入記憶體進行內部排序，生成若干個有序段並把它們寫到磁帶上；

（2）對這些有序段進行反覆合併；

（3）最後將有序段合併成一個包含檔案中所有記錄的有序段。

至此，檔案的外部排序過程就結束了。

影響因素

因為磁帶是順序存取的設備，存取數據快的時間與所存取的數據塊在磁帶上的位置有密切關係，所以有序段分布在不同磁帶上和在同一磁帶的不同位的情況對排序的效率有很大的影響。

兩種排序方法

平衡合併排序

所謂平衡排序是指在排序的過程中，進行下一遍合併之前必須把初始有序段或上一遍合併所產生的有序段均勻地分布到各輸入帶上。

與磁碟檔案的排序一樣，對磁帶檔案進行排序所需要的時間與掃描磁帶檔案的遍數有密切關係，採用k（≥2）路合併可以減少掃描磁帶檔案的遍數。

為了避免太多的磁帶尋找時間，當前被合併的有序段必須放在各台不同的磁帶機上。因此，k路合併在合併期間至少需要k台磁帶機作為輸入。另外還需要一台作為輸出。這樣，進行k路合併至少要有（k+1）台磁帶機。如果用（k+1）台磁帶機實現k路合併，那么需要對輸出帶另外做一遍掃描，把上一遍合併時所生成的有序段均勻地分布到k台機上作為下一遍合併之用。如果使用2k台就可以避免上述的重新分布有序段的問題，因為進行k路合併時，可用其中k台作為輸入，而其餘k台作為輸出。在對檔案進行下一遍合併時把輸出帶作為輸入帶，而把輸入帶作為輸出帶。