추가 설명 — 왜 하필 5개로 나누는가

선택 문제의 median of medians는 하필 5개씩 나눴다. 4도 6도 아닌 5인 이유를 따진다.

---

그룹 크기 g로 일반화

메인 글은 5개씩 묶는 이유를 짧게 예고만 하고 넘어갔다. 여기서는 그 이유를 처음부터 따진다.

$n$개의 원소를 $g$개씩 묶는다고 하자. 그러면 그룹이 $n/g$개 생긴다(편의상 $n$이 $g$의 배수라 가정한다). 각 그룹을 정렬해 그룹 중앙값 $X_i$를 구하고, 그 중앙값들의 중앙값 $X'$를 재귀로 찾는다.

$X'$ 이하임이 보장되는 원소가 몇 개인가?

$X'$는 $n/g$개의 그룹 중앙값 중 중앙값이므로, 그룹 중앙값의 절반—약 $\dfrac{n}{2g}$개—이 $X'$ 이하다. 이 그룹들은 각자 $\lceil g/2 \rceil$개씩 $X'$ 이하인 원소를 갖는다(그룹이 오름차순 정렬되어 있어, 중앙값 이하 원소가 정확히 $\lceil g/2 \rceil$개). 짝수 $g$에서는 가운데 두 값 중 아래쪽을 그룹 중앙값으로 삼기로 한다. 위쪽을 골라도 두 방향이 뒤바뀔 뿐 약한 쪽의 개수는 같으므로 결론은 변하지 않는다. 따라서:

$$\text{보장 원소 수} \approx \frac{n}{2g} \cdot \left\lceil \frac{g}{2} \right\rceil \approx \frac{n}{2g} \cdot \frac{g+1}{2} = \frac{n(g+1)}{4g}$$

$g$가 크면 $\dfrac{g+1}{4g} \to \dfrac{1}{4}$으로 수렴한다 — 아무리 그룹을 크게 묶어도 보장은 $n/4$ 근처를 넘지 않는다.

$g$	중앙값 이하 개수	보장 수식	근사
3	2	$\frac{n}{6} \cdot 2$	$\approx 0.333n$
4	2	$\frac{n}{8} \cdot 2$	$= 0.25n$
5	3	$\frac{n}{10} \cdot 3$	$= 0.3n$
6	3	$\frac{n}{12} \cdot 3$	$= 0.25n$
7	4	$\frac{n}{14} \cdot 4$	$\approx 0.286n$

짝수 줄이 둘 다 정확히 $0.25n$인 것이 눈에 띈다. 우연이 아니다. $g = 2k$에서 하위 중앙값 이하인 원소는 $k$개이므로

$$\frac{n}{2g} \cdot k = \frac{n}{2 \cdot 2k} \cdot k = \frac{n}{4}$$

로 $k$가 약분돼 사라진다. 짝수는 아무리 크게 묶어도 보장이 $n/4$에 고정된다. 홀수 $g$의 보장 $\frac{n(g+1)}{4g}$는 언제나 $n/4$보다 크므로, 짝수 $g$는 바로 아래 홀수인 $g-1$보다 보장이 작으면서 정렬 비용은 더 든다. 이것이 홀수를 쓰는 진짜 이유다.

---

선형이 되는 조건

보장 원소가 $\beta_0 n$개라면, $X'$를 pivot으로 쓸 때 재귀하는 쪽의 크기 상한은 $(1 - \beta_0)n$이다. 선택 알고리즘의 점화식은:

$$S(n) = \underbrace{S(n/g)}_{\text{중앙값 재귀}} + \underbrace{S\!\bigl((1-\beta_0)n\bigr)}_{\text{partition 후 재귀}} + O(n)$$

$S(n) \le cn$이라는 선형 상한이 닫히려면 두 재귀 인수의 비율 합이 1 미만이어야 한다. 이를 $\alpha$, $\beta$로 표기하면:

$$\alpha + \beta < 1 \qquad \text{여기서 } \alpha = \frac{1}{g},\; \beta = 1 - \beta_0$$

왜 합이 1 미만이어야 하는지 대입법으로 확인하자. $S(n) \le cn$을 가정하고 점화식에 넣으면:

$$S(n) \le 2n + \alpha cn + \beta cn = 2n + (\alpha + \beta)cn$$

이 우변이 다시 $cn$ 이하가 되려면 $2n + (\alpha+\beta)cn \le cn$, 즉 $2 \le (1-\alpha-\beta)c$여야 한다. $\alpha+\beta < 1$이면 $(1-\alpha-\beta)$가 양수이므로 충분히 큰 유한한 $c$를 잡을 수 있다. $\alpha+\beta = 1$이면 불가능하다.

---

g=5일 때

메인 글의 분석 그대로다. 그룹이 $n/5$개이므로 $\alpha = 1/5 = 0.2$. 보장 원소는 $\frac{n}{10} \times 3 = 0.3n$이므로 $\beta = 1 - 0.3 = 0.7$.

$$S(n) = 2n + S(0.2n) + S(0.7n), \quad \alpha + \beta = 0.2 + 0.7 = 0.9 < 1 \quad \checkmark$$

$(1 - 0.9)c \ge 2$를 풀면 $c \ge 20$. 즉 $S(n) \le 20n = O(n)$.

---

g=3일 때

그룹이 $n/3$개이므로 $\alpha = 1/3$. 보장 원소는 $\frac{n}{6} \times 2 = \frac{n}{3}$이므로 나머지는 $n - n/3 = \frac{2n}{3}$, 즉 $\beta = 2/3$.

$$S(n) = 2n + S\!\left(\frac{n}{3}\right) + S\!\left(\frac{2n}{3}\right), \quad \alpha + \beta = \frac{1}{3} + \frac{2}{3} = 1 \quad \times$$

비율 합이 정확히 1이다. 대입법은 $2n \le 0 \cdot cn$을 요구하므로 어떤 $c$도 맞지 않는다. 실제로 이 점화식은 $S(n) = \Theta(n \log n)$으로 풀린다.

---

g=7일 때

그룹이 $n/7$개이므로 $\alpha = 1/7$. 보장 원소는 $\frac{n}{14} \times 4 = \frac{2n}{7}$이므로 $\beta = 1 - 2/7 = 5/7$.

$$\alpha + \beta = \frac{1}{7} + \frac{5}{7} = \frac{6}{7} \approx 0.857 < 1 \quad \checkmark$$

선형이 성립하고, 비율 합 $\frac{6}{7} \approx 0.857$은 $g=5$의 $0.9$보다 작다. 보장 비율만 보면 $2/7 \approx 28.6\%$로 $g=5$의 $30\%$보다 작지만, $\alpha = 1/g$가 더 빨리 줄어 합은 오히려 내려간다. 수축만 놓고 보면 $g=7$이 $g=5$보다 낫다.

그렇다면 왜 5를 쓰는가. 위 점화식이 덧붙는 항을 $2n$으로 고정해 둔 것이 답을 한쪽으로 기울인다. 실제로는 그룹 하나를 정렬하는 비용이 $g$에 따라 늘어난다. $g$개를 최악에 정렬하는 데 필요한 최소 비교 횟수는 5개에서 7회, 7개에서 13회이므로 원소당 $1.4$회와 약 $1.86$회다. 덧붙는 항을 $a_g \cdot n$으로 두면 상수는

$$c = \frac{a_g}{1 - \alpha - \beta}$$

가 되어 분자와 분모가 함께 커진다. 어느 쪽이 이기는지는 비용 모형이 정한다.

$g$	비율 합 $\alpha+\beta$	정렬 최소 비교 (원소당)
5	$0.900$	7회 ($1.40$)
7	$0.857$	13회 ($1.86$)
9	$0.833$	19회 ($2.11$)

두 열이 반대 방향으로 움직인다. 그래서 “$g \ge 7$은 이득이 없다”고 단정할 근거는 이 분석 안에 없다. 확실한 것은 5가 조건을 만족하는 가장 작은 크기이고, 그래서 그룹 정렬을 손으로 펼쳐 쓰기에 가장 간단하다는 점이다. 관례가 5로 굳은 이유도 여기에 있다.

---

짝수는 왜 밀려나는가

짝수 $g$가 배제되는 이유를 “중앙값이 두 개라 모호하다”로 설명하면 틀린다. 가운데 두 값 중 아래쪽을 쓴다고 정해 두면 모호함은 사라지고, 위에서 본 대로 계산이 그대로 굴러간다. 짝수가 밀려나는 이유는 모호함이 아니라 수치다.

$g = 2k$에서 보장이 $k$에 상관없이 $n/4$로 고정된다는 것을 앞에서 보았다. 하위 중앙값 아래에 $2k$개 중 $k$개만 놓이므로, 그룹을 키워 얻은 원소가 약한 쪽에는 하나도 보태지지 않는다. 그래서 짝수 $g$는 언제나 $\beta = 3/4$이고, 비율 합은 $\frac{1}{g} + \frac{3}{4}$뿐이다.

$g$	$\alpha$	$\beta$	비율 합	선형?
3	$1/3$	$2/3$	$1$	✗
4	$1/4$	$3/4$	$1$	✗
5	$1/5$	$7/10$	$9/10$	✓
6	$1/6$	$3/4$	$11/12$	✓
7	$1/7$	$5/7$	$6/7$	✓

$g=4$가 탈락하는 이유는 짝수라서가 아니라 비율 합이 정확히 1이기 때문이다. $g=3$과 같은 방식으로 막힌다. 그리고 $g=6$은 짝수인데도 $11/12 < 1$로 선형이 성립한다. “짝수는 안 된다”는 일반 명제는 성립하지 않는다.

짝수가 실제로 지는 지점은 따로 있다. 모든 짝수 $g$는 바로 아래 홀수 $g-1$에 진다. $g=6$의 $11/12$는 $g=5$의 $9/10$보다 크고, $g=8$의 $7/8$은 $g=7$의 $6/7$보다 크다. 수축은 더 나쁜데 그룹 하나를 정렬하는 비용은 더 든다. 짝수를 고를 이유가 없는 것이지, 쓸 수 없는 것이 아니다.

이제 남은 후보를 작은 것부터 훑는다.

• $g=1$: 그룹 정렬이 없고 그룹 중앙값이 원소 자체다. 중앙값 재귀가 $S(n)$이 되어 진전이 없다.
• $g=2$: $\alpha = 1/2$, $\beta = 3/4$로 합이 $5/4 > 1$. 실패.
• $g=3$: 비율 합 $= 1$. 등식이라 실패.
• $g=4$: 비율 합 $= 1$. 등식이라 실패.
• $g=5$: 비율 합 $= 0.9 < 1$. 성립하는 가장 작은 크기.