Locality-aware Mergesort

Question

讓A成爲一個總排序順序的數組。我們說A具有局部性d iff每個元素最多d索引遠離其在排序數組中的最終索引。在感知局部性的mergesort中，我們只需要考慮中間的2d元素（最右邊的d元素位於右側子陣列中的左側子陣列和最左側d元素中），因爲其他元素必須處於其最終狀態位置。問題是如何證明局部感知mergesort的漸近時間性能爲n log d。

有其他排序算法的局部感知版本;感知局部性mergesort的表現是唯一一個我不明白的地方。

Answer 1

那麼它是有道理的。如果你想一想：合併排序是O（nlog n），對於每個元素（n個元素），最多需要log n個迭代才能達到陣列中的位置（項目可以「行進的最大距離「是n）。舉例來說，它只會記錄下來，因爲物品可以行進的距離被限制在d。至少我是這麼看的。