정렬 - 줄을 세우는 값과 그 대가

카드 게임에서 손패를 받으면 아무도 시키지 않았는데 정리부터 한다. 이유는 하나다. 정리해 두면 그다음 모든 일이 쉬워져서다.

손패를 정리하는 두 가지 손버릇

카드를 정리하는 방식은 사람마다 다르지만 크게 둘로 갈린다.

한 장씩 뽑아 제자리에 끼우는 사람이 있다. 왼쪽은 이미 정리된 구역이고, 새 카드를 왼쪽으로 밀어 넣으면서 자리를 찾는다.

반씩 나눠 놓고 합치는 사람도 있다. 손패를 둘로 갈라 각각 정리한 다음, 두 뭉치의 맨 앞장만 비교하며 하나로 합친다.

둘 다 결과는 같다. 다른 건 카드가 많아졌을 때 벌어지는 일이다.

한 장씩 끼우면 왜 느려지나

앞엣것부터 보자. 새 카드를 넣을 자리를 찾으려면 이미 정리된 부분을 훑어야 한다. 카드가 열 장이면 앞의 열 장, 스무 장이면 앞의 스무 장이다.

카드 한 장마다 그만큼을 훑으니 전체는 대략 n × n이다. 카드가 두 배가 되면 일은 네 배가 된다. 이게 삽입정렬이고, 같은 계열에 선택정렬과 버블정렬이 있다. 이름은 달라도 두 배에 네 배라는 모양은 같다.

그런데 이 방식이 거의 정렬된 데이터에서는 대단히 빠르다. 새 카드가 대부분 맨 끝에 그대로 들어가면 훑을 일이 거의 없어서, 실질적으로 한 바퀴만 돈다. 실무 정렬 라이브러리가 작은 조각에서 이 방식으로 갈아타는 이유가 이거다.

반씩 나눠 합치면 왜 빠른가

뒤엣것은 발상이 다르다. 정리하는 대신 나눈다. 나누고 나누다 보면 카드 한 장이 되고, 한 장은 이미 정리된 상태다. 그다음부터는 합치기만 한다.

합치는 게 싼 이유가 핵심이다. 두 뭉치가 각각 이미 정리되어 있으면, 더 작은 쪽의 맨 앞장은 무조건 두 뭉치를 통틀어 가장 작다. 양쪽 맨 앞장만 보면 된다. 뒤를 안 봐도 된다.

그래서 두 뭉치를 합치는 데 드는 일은 카드 수만큼이다. 나누는 깊이가 log n이고 각 깊이에서 카드 전체를 한 번씩 훑으니 n log n이 나온다. 이 이야기는 뒤에 볼 분할 정복에서 다시 자세히 본다.

셋째 줄이 퀵정렬이다. 기준값 하나를 잡아 작은 것과 큰 것으로 가른 다음 양쪽을 다시 가른다. **평균은 가장 빠른데 최악이 n²**이라, 실무 구현들은 기준값을 무작위로 고르거나 깊이가 깊어지면 다른 방식으로 갈아타서 최악을 피한다.

두 배보다 빠를 수는 없나

여기서 자연스러운 질문이 나온다. n log n보다 빠른 정렬은 왜 없을까.

값을 서로 비교해서 순서를 정하는 한 없다는 게 증명되어 있다. 비교 한 번은 “이 둘 중 누가 앞이냐”라는 예/아니오 하나이고, 카드 n장을 줄 세우는 경우의 수는 n!가지다. 예/아니오 하나로 후보가 절반씩 줄어드니, n!가지를 하나로 좁히려면 최소한 log(n!)번은 물어야 한다. 그 값이 대략 n log n이다.

그러니 n log n은 누가 게을러서 못 넘은 벽이 아니라 비교로 푸는 한 넘을 수 없는 벽이다. 넘으려면 비교를 안 하면 된다. 값의 범위를 미리 알고 있으면 값 자체를 자리 번호로 쓸 수 있고, 그러면 한 바퀴에 끝난다. 비교를 계산으로 바꾸는 것인데, 해시테이블이 쓰던 발상과 같다.

진짜 문제는 같은 값끼리다

실무에서 정렬로 겪는 버그는 대부분 빠르기와 상관이 없다. 값이 같은 것들의 순서에서 난다.

주문 목록을 이름순으로 정렬해 화면에 뿌린 다음, 사용자가 “금액순으로” 버튼을 누른다. 금액이 같은 주문 셋이 있다면 그 셋은 어떤 순서로 나와야 할까.

같은 값끼리는 원래 순서를 그대로 지키는 정렬을 안정 정렬이라고 한다. 안정적이면 금액이 같은 셋은 아까의 이름순을 유지한 채 나온다. 안정적이지 않으면 그 셋의 순서가 매번 달라질 수 있다.

이게 만드는 증상이 지독하다.

• 새로고침할 때마다 목록 중간의 순서가 미묘하게 바뀐다
• 개발 장비에서는 재현이 안 되고 데이터가 많은 운영 환경에서만 나타난다
• 페이지를 넘길 때 같은 항목이 두 번 보이거나 하나가 사라진다

마지막 줄이 실제로 아프다. 페이지를 나눠 주는 방식은 “몇 번째부터 몇 개”로 자르는데, 매 요청마다 순서가 흔들리면 경계에 걸친 항목이 중복되거나 빠진다. 정렬 기준을 하나 더 줘서 순서를 확정 짓는 것이 해법이고, 대개 그 하나는 고유한 값이다.

⚠️ 언어와 버전마다 안정성이 다르다. 자바의 객체 정렬과 파이썬의 sorted는 안정적이지만, 원시 타입 배열 정렬이나 병렬 정렬은 그렇지 않은 경우가 있다. “이 정렬이 안정적인가”는 문서를 봐야 하는 항목이지 짐작할 것이 아니다.

무엇을 기준으로 세울지도 절차다

정렬을 쓸 때 실제로 우리가 짜는 건 정렬 자체가 아니라 비교 기준이다. 그리고 여기가 조용히 깨지는 자리다.

비교 기준에는 지켜야 할 규칙이 있다. A가 B보다 앞이면 B는 A보다 뒤여야 하고, A가 B보다 앞이고 B가 C보다 앞이면 A는 C보다 앞이어야 한다. 당연해 보이지만 실무 코드에서 자주 깨진다.

// 위험: 뺄셈은 값이 크면 넘쳐서 부호가 뒤집힌다
list.sort((a, b) -> a.getAmount() - b.getAmount());

// 안전
list.sort(Comparator.comparingInt(Order::getAmount));

기준이 어긋나면 정렬 결과가 이상해지는 정도로 끝나지 않는다. 자바는 이걸 발견하면 아예 예외를 던지고 멈춘다. 틀린 순서를 조용히 내놓느니 멈추는 쪽을 고른 것이다.

실무에서: 대개 정렬은 내 코드 밖에서 일어난다

목록을 정렬해서 보여주는 화면이 있다면, 그 정렬은 십중팔구 애플리케이션이 아니라 데이터베이스가 한다. ORDER BY 한 줄이다.

그러면 이 글의 내용이 필요 없을까. 오히려 여기서 값을 한다.

• 정렬은 공짜가 아니다. 인덱스 순서와 ORDER BY가 맞으면 DB는 이미 정렬된 것을 읽기만 하지만, 어긋나면 결과를 전부 모아 따로 줄을 세운다. 실행 계획에 나타나는 정렬 단계가 그 신호다.
• 정렬을 애플리케이션으로 가져오면 전부 메모리에 올려야 한다. DB가 100만 건을 정렬하는 것과, 100만 건을 받아와 정렬하는 것은 전혀 다른 비용이다.
• 정렬하지 않고 상위 몇 개만 필요하다면 정렬 자체가 과하다. 꼭대기 하나만 약속하는 그릇을 쓰면 전부 줄 세울 이유가 없다.

정리하면 실무에서 물어야 할 것은 “어떤 정렬 알고리즘인가”가 아니다. 어디서 정렬되는가, 안정적인가, 애초에 정렬이 필요한가. 셋이다.

정리

• 정렬 방식은 크게 **한 장씩 끼우기(두 배에 네 배)**와 **반씩 나눠 합치기(두 배에 두 배 조금)**로 갈린다.
• 합치기가 싼 이유는 양쪽이 이미 정렬되어 있어 맨 앞장만 보면 되기 때문이다.
• 비교로 푸는 한 n log n이 벽이다. 넘으려면 비교를 계산으로 바꿔야 한다.
• 실무 버그는 대개 빠르기가 아니라 같은 값끼리의 순서에서 난다. 안정 정렬인지 확인할 것.
• 페이지를 나눠 줄 때는 순서를 확정 짓는 기준을 하나 더 준다. 안 그러면 항목이 중복되거나 사라진다.
• 실무의 질문은 셋이다. 어디서 정렬되나, 안정적인가, 정렬이 정말 필요한가.

다음 글은 정렬해 두면 열리는 문 하나를 본다. 줄이 서 있으면 절반을 그냥 버릴 수 있다.