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.