정렬 · 알고리즘, 인생을 계산하다

훅 — 양말 사건

MIT 학부생 시절 Danny Hillis의 룸메이트는 빨래 통에서 양말을 두 개씩 무작위로 꺼내, 짝이 안 맞으면 다시 던져 넣는 방식을 썼습니다. 10쌍이라면 첫 짝까지 평균 19번, 두 번째 짝까지 17번 더, 총 110번. Hillis는 "기숙사 방 변경을 신청하고 싶었다"고 회고합니다.

심지어 튜링상 수상자 Ron Rivest도 인정합니다 — "Socks confound me!"(양말은 날 혼란스럽게 한다). 인터뷰 당시 그는 샌들을 신고 있었다고요.

컴퓨터 과학의 첫 가르침

Scale Hurts (규모는 아프다)

일반 비즈니스의 "규모의 경제" 직관과 정반대로, 정렬에서는 두 배가 네 배가 됩니다. 그래서 컴퓨터 과학자가 거꾸로 말합니다 —"정렬할 가치가 없는 것을 정렬하지 마라."

O(1)

상수

카디널 측정. 마라톤 순위.

O(n)

선형

버킷 정렬. 토너먼트.

O(n log n)

이론적 한계

Mergesort. 비교 정렬의 끝.

O(n²)

이차

Bubble Sort. n=100일 때 100×100=10,000번.

Mergesort의 분할정복 — 반으로 쪼개고, 정렬된 더미를 지퍼처럼 합친다. O(n log n).

직접 해보기

정렬 알고리즘 레이스

🏁 정렬 알고리즘 레이스

20개 숫자 — 비교 횟수

Bubble Sort · O(n²)

인접한 두 개를 비교해서 교환. 작지만 모든 쌍을 확인해야 함.

Mergesort · O(n log n)

반으로 쪼개고, 정렬된 더미를 합친다. 분할정복.

💡 데이터가 두 배가 되면 Bubble Sort는 4배 느려지지만, Mergesort는 약 2.2배만 느려집니다. 인구조사급 데이터에서 차이는 수억 번의 작업으로 벌어집니다.

Lewis Carroll(Dodgson)의 발견 — 진짜 2등이 2등 메달을 받을 확률은 16/31.

대중 정치인의 등장

👤 버락 오바마· 2007 구글 방문

Eric Schmidt가 농담으로 "백만 개 32비트 정수를 정렬하는 가장 좋은 방법은?"이라고 묻자, 오바마는 즉답: "Bubble Sort는 잘못된 방법이겠지요." 구글 직원들의 환호를 받았습니다.

👤 Charles Dodgson (Lewis Carroll)· 1883

《이상한 나라의 앨리스》의 작가는 옥스퍼드 수학 강사이기도 했습니다. 한 잔디 테니스 선수가 "제가 아는 열등한 선수가 2등 메달을 받았다"고 한탄한 데서 영감을 받아 토너먼트를 분석했죠.

결론: Single Elimination(단일 패자전)에서 진짜 2등이 2등 메달을 받을 확률은 16/31에 불과. "은메달은 거짓말이다."

실제 정렬 챔피언십

👤 Preston Sort Center · King County Library· 워싱턴주

2011, 2013 National Library Sorting Champion. 분당 167권, 일 8.5만 권을 96개 빈에 분류합니다. NYPL과 매년 챔피언십을 다투는데, 2014년 NYPL의 Salvatore Magaddino 답변: "Fuhgeddaboutit"(킹카운티 우리 못 이겨).

👤 Jordan Ho (UC Berkeley 화학 전공)

150권의 책을 40분 미만에 정렬. 그의 전략: "3500대 책이 많다는 걸 알아. 3500 미만을 먼저 분류하고, 3500-3599 분리, 더 세밀히 3510s, 3520s..." — 정확한 Bucket Sort 후 Insertion Sort.

가장 깊은 통찰

Race vs Fight

마카크 원숭이 무리는 위계가 명확할 때 폭력이 줄어듭니다(Jessica Flack의 연구). 닭 무리도 마찬가지인데, 부리를 자르는(debeaking) "친절한" 처치는 정렬 메커니즘을 제거해 오히려 공격성을 키웁니다.

인간 사회의 위대한 발명은 ordinal에서 cardinal로의 도약입니다. 돈, 나이, GDP — 이 카디널 척도들 덕분에 매번 군사 충돌이나 협상으로 정렬할 필요 없이, 이미 "정렬된" 상태로 사회가 돌아갑니다.

"매일의 쥐 경주를 한탄하지만, 그것이 싸움이 아니라 '경주'라는 점이야말로 우리를 원숭이, 닭, 그리고 쥐와 구분 짓는 핵심이다."
— 챕터 결언

실생활 적용

📚 책장 정렬: 알파벳순 정렬은 거의 시간낭비. 검색이 더 빠르다.
📧 이메일 폴더링: 대부분 시간낭비 — 그냥 검색하라.
🧦 양말 정리: 빨래 빈도를 늘려라. 14일→13일이면 28번 적게 꺼낸다.
🏆 스포츠: 진짜 1등을 가리기보다 시즌 내내 긴장을 유지하기 위해 일부러 비효율적 토너먼트를 사용한다.

💭

Reflection

고민해 볼 질문들

정답이 정해져 있지 않은 열린 질문입니다. 혼자 생각해 보거나, 가까운 사람과 함께 이야기 나눠 보세요.

01
당신이 '굳이 정렬하지 않고도' 잘 살고 있는 영역은 무엇인가요? 그 어수선함이 사실은 합리적이라면요?
02
당신을 둘러싼 위계(직장·가족·친구)는 어떤 카디널 척도로 결정되나요? 그 척도는 공정한가요?
03
잡음이 많은 평가 환경(사람·예술·취향)에서 당신은 빠른 알고리즘을 쓰고 있나요, 견고한 알고리즘을 쓰고 있나요?
04
도서관처럼 정렬에 거대한 비용을 들일 가치가 있는 것과, 그냥 검색해서 살아도 되는 것의 경계는 어디일까요?