如何計算就地外部合併排序的時間？

Question

原始問題如下：
您將排序1PB大小的整數範圍從-2^31〜2^31 - 1（int），您有1024臺機器，每臺機器具有1TB磁盤空間和16GB內存空間。假設磁盤速度爲128MB/s（r/w），內存速度爲8GB/s（r/w）。 CPU的時間可以忽略。爲簡單起見，網絡傳輸時間可以忽略。計算所需的近似時間。

我知道與外部排序，我們可以在大致10小時作爲計算這樣一臺機器上的1TB的數據進行排序：

磁盤訪問（2r2w）：1T * 4/128MB/S = 2^15秒〜 9小時
存取訪問：
排序2^48 64個部分（每個2^42）的整數大概每個需要1.3分鐘。所以總共1.4小時。
63路合併需要幾秒鐘，因此被忽略。

但是下一步怎麼樣：1024T數據的組合？我不知道這是如何計算的。請幫忙嗎？

Answer 1

2^31 = 20億（2「giga」）。所以你正在看很多重複的數字和固定的範圍。所以考慮基底排序（http://en.wikipedia.org/wiki/Radix_sort）。

每個處理器，對於od數據子集）創建'count'數組（x [0]包含0等的計數）。然後你可以將所有結果合併成一個數組。稍後，您可以「構建」已排序的數組。