어떻게 더 똑똑하게 줄 세워요

한 칸씩은 느리다

앞 레슨의 방법은 단순해서 좋았다. 옆끼리 견주고 큰 것을 뒤로 보내면 됐다.
그런데 줄이 길어지면 견줄 일이 너무 많아진다.
카드가 두 배가 되면 비교는 네 배로 뛴다. 넷이면 금방이지만 서른둘이면 까마득해요.

줄을 두 배로 늘려 본다. 길이 두 배 → 비교는 네 배로 폭증.

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

반으로 쪼갠다

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

한 묶음을 계속 반으로 쪼갠다. 8 → 4+4 → 2+2+2+2 → 한 칸씩.

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

정렬된 둘을 합친다

정렬된 두 묶음을 한 줄로 합칠 때 비결은 맨 앞만 보는 것이다.
두 묶음의 첫 칸을 견줘 작은 쪽을 결과로 떨군다. 그 자리는 다음 칸이 채우고, 또 첫 칸끼리 견준다.
지퍼를 채우듯 한 칸씩 맞물려 합쳐져요.

두 묶음의 맨 앞을 견줘 작은 쪽을 떨군다. 지퍼처럼 한 칸씩 합친다.

신기한 일이다. 뒤죽박죽인 전체를 견줄 때는 느렸는데, 저마다 정렬된 둘을 합칠 때는 맨 앞만 보면 되니 빠르다.
쪼개기 덕분에 작고 정렬된 조각이 생기고, 그 조각들을 차곡차곡 합치면 어느새 온전한 줄이 돼요.

왜 빠를까: 층의 수

이 방법은 왜 더 빠를까?
반으로 쪼개니 쪼개는 층이 얼마 되지 않는다. 줄이 두 배가 되어도 층은 딱 하나만 는다.
한 층을 합치는 비용은 줄 길이만큼이라, 전체 비용은 층 수 곱하기 줄 길이다.
한 칸씩 견줄 때(길이 곱하기 길이)보다 훨씬 천천히 커져요.

층을 펼치고 줄 길이를 바꿔 본다. 층 수 x 한 층 = 한 칸씩보다 천천히 커진다.

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

정리

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

네 단계를 차례로 누르며 한 바퀴 따라간다. 쪼개기 → 한 칸 → 합치기 → 층 수만큼 = 빠름.

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