Mo's Algorithm의 정렬은 왜 하필 "x[0] // sqrt_N" 일까? (기하학적 해석)

Mo's Algorithm을 처음 접하면 가장 의아한 부분이 바로 쿼리 정렬 기준입니다.

# 보통의 정렬
queries.sort() 

# Mo's Algorithm 정렬
queries.sort(key=lambda x: (x[0] // sqrt_N, x[1]))

왜 그냥 시작점(L)이나 끝점(R)으로 정렬하지 않고, 굳이 제곱근으로 나눈 몫(Block)을 기준으로 정렬할까요?
어려운 수식은 제외하고, 이 글에서는 2차원 좌표 평면 위에서의 경로 이동을 직접 그려보며 그 이유를 직관적으로 알아보려고 합니다.

---

1. input 가정

우리가 처리해야 할 쿼리 $(L, R)$이 다음과 같은 패턴으로 들어온다고 가정해 봅시다.
($N$=100, $R$은 조금씩 증가하지만 $L$은 양 끝을 오가는 상황)

• Query 1: (1, 50)
• Query 2: (49, 51)
• Query 3: (2, 52)
• Query 4: (48, 53)
• ...

Mo's 알고리즘의 증명을 보다보면, 대부분 직선 위에서, 다음과 같은 그림을 보게 됩니다.

보통의 증명들은 이 쿼리 를 "$sqrtN$ 사이즈로 어찌어찌 잘" 정렬해서 시간복잡도를 줄일 수 있다고 하는데,,,
정렬된 값을 보더라도 잘 와닿지는 않더라구요.

그렇다면 이 데이터를 좌표 평면의 점 $(x, y) = (L, R)$로 찍어보면, 포인터의 이동 경로는 어떻게 그려질까요?

(실수로 x축의 값을 98, 99로 올렸네요 48, 49로 감안하고 읽어주세요 ㅜㅜ)

---

2. 정렬 방식별 이동 경로 비교

데이터에 따라, 어떤 데이터는 ①이 빠를수도, ②가 빠를수도 있습니다.
그 이유를 알아봅시다.

① 끝점 기준 정렬 (Key = x[1])

queries.sort(key=lambda x: x[1])

$R$ 좌표를 기준으로 정렬했으므로, $R$ 포인터는 50, 51, 52... 아주 얌전하게 움직입니다. 하지만 이때 $L$ 포인터는 어떻게 될까요?

• 동작: $R$은 편안하지만, $L$이 매 쿼리마다 1에서 49로, 다시 2로, 다시 48로 운동장을 가로지르는 왕복 달리기를 합니다.
• 비용: $L$ 혼자서 $O(N \times M)$의 이동을 감당해야 합니다. (시간 초과)

② 시작점 기준 정렬 (Key = x[0])

queries.sort(key=lambda x: x[0])
# [재배치된 순서]
# (1, 50), (2, 52), (3, 54), (4, 56) ... (46, 57), (47, 55) ...

반대로 $L$ 좌표를 기준으로 정렬하면 어떻게 될까요? 이 특정한 데이터에서는, 운 좋게 효율적으로 스위핑을 하는 것 처럼 보입니다.

하지만 만약
입력 데이터가 (1, 100), (2, 2), (3, 100) 처럼 들어온다면, 이번엔 $R$ 포인터가 위아래로 미친 듯이 널뛰기를 합니다.

• 비용: 마찬가지로 $O(N \times M)$ 발생.

결국 단순한 $x$축, $y$축 정렬은 한쪽을 고정시키는 대신 다른 한쪽을 희생양으로 삼는 구조입니다.

---

3. Mo's 정렬 (Key = x[0] // sqrt_N) : 기하학적 최적화

어떠한 데이터가 들어올지 모르는 상황에서,
Mo's Algorithm은 이 문제를 해결하기 위해 "타협"을 합니다. $L$을 완벽하게 정렬하는 대신, 구역(Block) 안에 가둬두는 것입니다.

sqrt_N = int(N ** 0.5)
queries.sort(key=lambda x: (x[0] // sqrt_N, x[1]))

이 방식은 2차원 평면을 세로로 길게 자른 뒤(Block), 각 조각 내부를 훑고 지나가는 방식입니다.

왜 이 방식이 효율적인가?

1. L의 관점 (구역 이동): $L$은 같은 블록($\sqrt{N}$ 크기) 안에서만 움직입니다. 블록을 넘어갈 때만 큰 이동을 합니다.
2. R의 관점 (단방향 스윕): $L$이 같은 블록에 묶여있는 동안, $R$은 지그재그 없이 오름차순(한 방향)으로 쭉 이동합니다.

즉, "거미줄 같은 무작위 이동"을 "뱀처럼 이어지는 부드러운 이동"으로 강제하여 경로의 총 길이를 최소화하는 것입니다.

---

4. 결론

Mo's Algorithm의 정렬 조건은 단순한 수식이 아닙니다.
이는 $L$과 $R$ 그 누구도 장거리 왕복을 하지 못하도록 '적당한 족쇄(Block)'를 채워,
최악의 경우에도 실행 시간을 수학적으로 보장($O((N+M)\sqrt{N})$)하는 기하학적 테크닉입니다.

알고리즘 문제에서 "운에 맡기는 정렬" 대신 "결과를 보장하는 정렬"이 필요한 이유입니다.