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.

Auto comment: topic has been updated by GreenLantern__1 (previous revision, new revision, compare).The thing is, we need to ensure that 2 intervals (

a_{1},b_{1}), (a_{2},b_{2}) are sorted such that, in this case, implies that the intervals will be in the same block. So we, need to compare with . first. If they are equal, then we need to ensure that eitherb_{1}≤b_{2}orb_{1}≥b_{2}holds for every interval in that block (i.e. the right pointer must be non-decreasing or non-increasing within a block).Now, if you simply sort by the condition

a_{1}<a_{2}, how do you sort byb_{1}andb_{2}in the same block?Thank you for replying.

Let's say there are two indexes

`b and c`

to the right of another index`a`

. Then if after sorting on the basis of`sqrt(N)`

b lies in the same block as a and c is in different block, then b will be nearer to a than c in the sorted container. Something like a,b,c.Then even without sorting using

`sqrt(N)`

b will be nearer to a than c in the sorted container.Won't it?And for indexes same, we can use the right pointer as a parametric right?

Well. You can sort purely by left pointer and still fulfill the condition that I mentioned for the left pointers. BUT, you will need to do some additional work. Because, the right pointer in each block is not necessarily non-increasing/non-decreasing anymore. So you will need to loop through each block and sort your elements by right pointer.

Why do more work then necessary? You can simply make one comparator which implements the comparison logic that I mentioned and everything will be good in one sort.

In Mo's, if we have (

a/c) = = (b/c) then we sort queries on the basis of the right pointer, in which it is possible that some query [l_{1},r_{1}] will come after [l_{2},r_{2}] even whenl_{1}<l_{2}.While sorting it just on the basis of the left pointer will not ensure us

O(sqrt(N)) time complexity.I have no idea what you are talking about. In Mo's algorithm we categorize based on left pointers (put in sqrt bucket) then sort by right pointers. Converesly, it is possible to categorize on right pointers and sort by left pointer but that's weird so I don't see an obvious reason to do so.

We never categorize by left/right pointer AND sort by the same pointer (there would be no point in doing so).

If you have an apple, then you have a fruit. But if you have a fruit, you don't necessarily have an apple.

What you are missing is that

`(a/c)`

is actually`floor(a/c)`

, so`a<b`

does not imply`(a/c)<(b/c)`

. Try`a = 5, b = 6, c = 4`

To understand Mo's algorithm, see LanceTheDragonTrainer's reply.

Sorting by (a/c)<(b/c) is splitting the array to blocks of size

cand sorting by which block the left pointer is in. Let's analyze running time according toc,n,q(n/c blocks of size c):O(c) moves. In the worst case it will also move over all blocks in all queries, so that'sO(n). We get its work to beO(cq+n).O(n), which gives .We want to minimize according to

c. Choosing we get while choosing we get . Even though the first one is always faster (according to math, but while ignoring the small change in constant), they probably have no difference in practice, especially whenn=q(but the more they differ, the better the first one is in comparison to the second one).Notice that by the formula, sorting by

a<bis havingc= 1, which has a complexityO(n^{2}) worstcase.Thank you so much. This makes sense.