The standard MO sorting has a hidden inefficiency. When moving to a new -block, might jump from high to low, causing movement.
Fix: alternate sorting direction of for odd vs even -blocks. plaintext sort queries by: primary key: floor(l / B) secondary key: r if block is even, else -r This zigzag pattern makes sweep back and forth instead of jumping.
In practice, this can speed up MO's algorithm by or more. The total complexity is still , but the constant factor improves significantly. Time: . Space: .