Why do we sort the left pointer by sqrt(N) in Mo's Algorithm?

Правка en2, от TooGoodToLoose, 2018-09-14 01:13:47

In Mo's Algorithm, we sort the left pointer by using sqrt(N).

However if we consider two left pointers a and b such that a<b then (a/c)<(b/c) where c=sqrt(N). Thus it won't matter if we sort it by a<b or (a/c)<(b/c).

I know I am missing something, but I can't figure it out.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский TooGoodToLoose 2018-09-14 01:14:07 0 (published)
en2 Английский TooGoodToLoose 2018-09-14 01:13:47 10 (saved to drafts)
en1 Английский TooGoodToLoose 2018-09-14 01:04:11 345 Initial revision (published)