더 똑똑하게 줄 세워요

한 칸씩은 느려요

지난번 방법은 단순해서 좋았어요.
옆끼리 견주고, 큰 걸 뒤로.
근데 줄이 길어지면
견줄 일이 너무 많아져요.
카드가 두 배가 되면
비교는 네 배로 뛰어요.
넷이면 금방이지만,
서른둘이면 까마득해요.

줄을 두 배로 늘려 봐요. (길이 두 배 → 비교는 네 배로 폭증)

막대가 무섭게 차오르죠.
줄이 길어질수록
느림이 더 심해져요.
문제는 줄 전체를
한 덩어리로 보고
끝까지 견주는 데 있어요.
그럼 덩어리를
쪼개 보면 어떨까요?

반으로 쪼개요

긴 줄을 통째로 다루지 말고,
반으로 쪼개 봐요.
그 반쪽도 또 반으로,
또 그 반쪽도 반으로.
계속 쪼개면
마지막엔 한 칸짜리만 남아요.
그런데 한 칸은
이미 정렬된 셈이에요.
혼자라서 견줄 게 없거든요.

한 묶음을 계속 반으로 쪼개 봐요. (8 → 4+4 → 2+2+2+2 → 한 칸씩)

쪼개기만 하면 끝일까요?
아니에요, 쪼갠 건
다시 모아야 줄이 되죠.
한 칸짜리들을
둘씩 짝지어 합치고,
그 합친 걸 또 합치고.
그런데 정렬된 둘을
합치는 일이 의외로 쉬워요.
다음에서 봐요.

정렬된 둘을 합쳐요

정렬된 두 묶음이 있어요.
둘을 한 줄로 합치는데,
비결은 맨 앞만 보는 거예요.
두 묶음의 첫 칸을 견줘
작은 쪽을 결과로 떨궈요.
그 자리는 다음 칸이 채우고,
또 첫 칸끼리 견주고.
지퍼를 채우듯
한 칸씩 맞물려 합쳐져요.

두 묶음의 맨 앞을 견줘 작은 쪽을 떨궈요. (지퍼처럼 한 칸씩 합치기)

신기하지 않아요?
뒤죽박죽 전체를 견줄 땐 느렸는데,
각자 정렬된 둘을 합칠 땐
맨 앞만 보면 되니 빨라요.
쪼개기 덕에
작고 정렬된 조각이 생기고,
그 조각들을 차곡차곡 합치면
어느새 온전한 줄이 돼요.

왜 빠른가, 층의 수

왜 이게 더 빠를까요?
반으로 쪼개니까
쪼개는 층이 얼마 안 돼요.
줄이 두 배가 돼도
층은 딱 하나만 늘어요.
그리고 한 층을 합치는 비용은
줄 길이만큼이에요.
그래서 전체 비용은
층 수 곱하기 줄 길이.
한 칸씩(길이 곱하기 길이)보다
훨씬 천천히 커지죠.

층을 펼치고 줄 길이를 바꿔 봐요. (층 수 x 한 층 = 한 칸씩보다 천천히 큰다)

정확한 수식은 나중에 더 배워요.
지금은 느낌만 가져가요.
반으로 쪼개면
층은 더디게 늘고,
각 층은 가볍게 합쳐지니까,
전체가 빨라진다는 것.
쪼개고 합치는 이 한 수가
속도를 확 바꿔 놓는 거예요.

정리해 봐요

한 줄로 꿰면 이래요.
한 칸씩 견주는 정렬은
줄이 길수록 느려요.
그래서 줄을 반으로 쪼개고,
끝까지 쪼개면 한 칸짜리,
곧 이미 정렬된 조각이 돼요.
그 정렬된 둘을 지퍼처럼 합치면,
층 수만큼만 합치면 되니
온 줄이 훨씬 빨리 맞아요.
쪼개고 합치기.
이게 똑똑한 정렬의 핵심이에요.

네 단계를 차례로 눌러 한 바퀴 따라가 봐요. (쪼개기 → 한 칸 → 합치기 → 층 수만큼 = 빠름)

여기서 합치기는 늘 차분히 반씩 나눴죠.
그런데 나누는 기준을
조금 다르게 잡는 사촌도 있어요.
가운데가 아니라
어떤 한 칸을 기준 삼아
작은 것과 큰 것으로 가르는 방법이에요.
그 기준을 어떻게 고르냐는
나중 이야기로 남겨 둘게요.
오늘은 이것만 가져가요.
반으로 쪼개고 합치면 빨라진다.