CODEWITHSUNDEEP
performancealgorithmsorting
Kaa1el
Kaa1el

Reputation: 337

locality-aware Mergesort

Let A be an array with a total order to be sorted. We say A has locality d iff each element is at most d indices away from its final index in the sorted array. In the locality-aware mergesort, instead of merging the two subarrays entirely, we only need to consider the middle 2d elements (rightmost d elements in the left subarray and leftmost d elements in the right subarray), since other elements must be in their final position. The question is how to show that the asymptotic time performance for the locality-aware mergesort is n log d.

There are locality-aware versions for other sorting algorithms; the performance for the locality-aware mergesort is the only one that I don't understand.

Upvotes: 1

Views: 907

Answers (1)

Muli Yulzary
Muli Yulzary

Reputation: 2569

Well it makes sense. if you think about it: merge sort is O(nlog n), for each element (n elements) it would take a maximum of log n iterations for it to be in its place in the array (the maximum distance an item can "travel" is n). For your example it would only be log d be because the distance the item can travel is capped at d. at least that is how I see it.

Upvotes: 1

Related Questions