파이썬·자바 정렬 성능 판단표, key·Comparator 고르는 법과 비용

파이썬 sorted() 와 자바 객체 정렬(List.sort(), Arrays.sort(Object[]))은 둘 다 Timsort 라서, 같은 100만 건이라도 입력 모양에 따라 비교 횟수가 18배 넘게 달라져요. 결론부터 말하면 실무에서 손볼 곳은 알고리즘이 아니라 정렬을 부르는 방식이에요. 정렬된 목록에 한 건씩 넣으며 매번 sort() 를 부르지 말고, 상위 몇 개만 필요하면 heapq 를, 비교 함수 대신 key= 를, 자바 숫자는 int[] 를 쓰는 것만으로 수십 배가 갈려요.

정렬 내부 구조(런·병합·갤로핑)는 안다고 보고, 이 글은 고를 때 필요한 숫자만 다뤄요. 아래 측정은 모두 Apple M1(8코어)에서 파이썬 3.14.8 과 OpenJDK 24.0.2 로 직접 돌린 값이에요. 절대 시간은 기기마다 다르니 배수로 읽어 주세요.

입력 모양별 비교 횟수, 정렬된 데이터는 거의 공짜예요

CPython listsort.txt 가 설명하듯 Timsort 는 이미 정렬된 구간을 찾아 그대로 써요. 실무에서 흔한 "정렬된 목록 뒤에 새 데이터가 붙은" 모양을 만들어 비교 횟수를 셌어요. functools.cmp_to_key 로 비교 함수를 감싸 호출 수를 세는 방식이에요.

import random
from functools import cmp_to_key

def count_compares(data):
    n = 0
    def cmp(a, b):
        nonlocal n
        n += 1
        return (a > b) - (a < b)
    sorted(data, key=cmp_to_key(cmp))
    return n

N = 1_000_000
base = list(range(N))
for k in (10, 1_000, 10_000, 100_000):
    random.seed(k)
    tail = random.sample(range(N), k)        # 정렬 안 된 새 데이터
    print(k, count_compares(base + tail))

뒤에 붙은 건수가 전체의 1% 이하면 비교 횟수는 n 과 거의 같아요. 10%를 넘으면 늘기 시작하지만 그래도 무작위보다 5배 적어요. 시간도 같은 흐름이었어요. 무작위 100만 정수는 1,216ms, 이미 정렬된 것은 21ms, 역순은 29ms, 뒤에 1,000건 붙은 것은 24ms 였어요.

그래서 시간순으로 쌓이는 로그·이벤트는 늦게 도착한 일부만 섞여 있으면 사실상 한 번 훑는 비용으로 정렬돼요. 시간순으로 커지는 키(예: UUIDv7)가 유리한 이유와도 이어져요(UUID vs 자동증가 기본키 글). 반대로 벤치마크를 정렬된 샘플로만 돌리면 운영에서 수십 배 느려질 수 있으니 무작위 입력을 꼭 하나 넣어요.

상황별 정렬 방법 판단표

heapq 문서도 nsmallest·nlargest 는 k 가 작을 때 유리하고, k 가 크면 sorted() 가, k=1 이면 min()·max() 가 낫다고 적어요. 실측에서 갈림길은 k 가 n 의 몇 % 수준일 때였어요. 1,000개까지는 시간이 거의 늘지 않다가 10만 개(10%)에서 정렬보다 2배 느려졌어요.

정렬된 목록에 값을 넣는 세 가지 방법은 차이가 훨씬 커요. 10만 건짜리 정렬된 목록에 무작위 값 1만 건을 넣는 데 걸린 시간이에요.

bisect 문서는 insort 의 탐색은 O(log n) 이지만 느린 O(n) 삽입 단계가 지배한다고 적어요. 조회가 넣기보다 드물면 모아서 한 번 정렬하는 쪽이 이기고, 매번 정렬된 상태로 읽어야 하는데 건수가 수십만을 넘으면 DB 인덱스 같은 다른 저장 구조를 따져 볼 때예요.

자바의 기본형 배열은 Timsort 가 아니라 Dual-Pivot Quicksort 로 정렬되고, 박싱이 없어 객체 비교 호출도 없어요. 같은 100만 개 난수를 int[] 로 정렬하면 237ms, Integer[] 는 1,006~1,079ms, Comparator.comparingInt 를 붙이면 1,086~1,257ms 였어요(워밍업 후 10회 중 마지막 3회). 자바 Arrays 문서에 따르면 객체 정렬은 안정적이라고 보장되니, 숫자만 정렬하고 같은 값의 순서가 의미 없을 때만 int[] 로 바꿔요.

parallelSort 는 무조건 빠르지 않아요. OpenJDK Arrays.java 의 MIN_ARRAY_SORT_GRAN 은 1 << 13(8,192)이고, 이보다 작거나 병렬 풀이 한 개뿐이면 그냥 순차 정렬로 돌아요. 100만 개 Integer[] 에서는 약 4배 빨랐지만, 웹 요청 스레드 안에서 부르면 공용 ForkJoinPool 을 다른 요청과 나눠 쓴다는 점을 같이 따져야 해요.

key 함수와 비교 함수, 시간과 메모리 비용 계산

파이썬 정렬 HOWTO 는 key 함수가 입력 원소마다 정확히 한 번만 불린다고 적어요. 반면 cmp_to_key 로 감싼 비교 함수는 비교마다 파이썬 함수를 불러요. 무작위 100만 정수 기준으로 재 보면 차이가 뚜렷해요.

메모리는 listobject.c 구조로 직접 계산할 수 있어요. 64비트에서 포인터 하나는 8바이트예요.

• key 없이 정렬: 병합용 임시 공간이 최대 n/2 포인터예요. 100만 건이면 500,000 × 8 = 4MB. 이미 정렬된 입력은 병합이 없어 0이었어요.
• key 를 주면: 키 배열 n 포인터(8MB)에, 병합 때 키와 원소를 같이 옮기느라 임시 공간이 두 배(8MB)가 되고, 키 객체 자체가 더해져요. key=lambda x: -x 는 새 정수 100만 개(개당 32바이트 할당)라 합계 48MB 였어요.
• 문자열 key: 최대 6자리 숫자 문자열 100만 개를 key=str.lower 로 정렬하니 새 문자열 때문에 62.9MB 였어요.
• sorted(): 새 리스트 8MB 가 추가돼 key 없이 12MB 였어요.

모두 tracemalloc 최고점이에요. 정리하면 key 정렬의 추가 메모리는 대략 16바이트 × n + 키 객체 크기 × n 이에요. 1,000만 건이면 이것만 수백 MB 라, 메모리 한도가 작은 컨테이너에서는 키가 새 객체를 만들지 않게(이미 있는 속성을 가리키는 attrgetter 등) 해요.

자바 TimSort.java 의 임시 배열도 처음엔 최대 256칸으로 시작해 필요하면 n/2 까지 커져요. 참조가 4바이트(압축 참조)면 1,000만 건에 20MB 예요. LinkedList 처럼 sort 를 직접 구현하지 않은 리스트는 List 인터페이스 기본 구현대로 toArray() 로 통째로 복사한 뒤 정렬해서 n 칸이 더 들어요.

기준이 여러 개일 때, 튜플 키보다 빠른 방법

부서 → 사번처럼 기준이 둘인 100만 건 (x % 100, x) 튜플을 정렬해 봤어요.

튜플 비교는 앞 칸이 같으면 뒤 칸까지 비교하는 일을 원소마다 반복해요. 앞 칸 값이 100가지뿐이라 동점이 많아 더 비쌌어요. 두 번 정렬은 정렬이 안정적이라 가능해요. 파이썬 stdtypes 문서가 sort() 의 안정성을 보장하니, 뒤 기준으로 먼저 정렬하고 앞 기준으로 다시 정렬하면 앞 기준이 같은 행끼리는 뒤 기준 순서가 남아요. 두 결과가 튜플 정렬과 같은지도 확인했어요.

자바는 보통 Comparator.comparing(Emp::dept).thenComparingInt(Emp::no) 한 번이 읽기 쉬워요.

자바 Comparator 오류, 언제 예외가 나고 언제 조용히 틀리나

Comparison method violates its general contract! 는 Comparator 문서의 규약(부호 대칭, 추이성)을 어긴 비교 함수를 OpenJDK TimSort.java 의 병합 단계가 알아챘을 때 나와요. 문제는 항상 알아채지는 못한다는 점이에요. 전 범위 난수 int 목록을 (x, y) -> x - y 로 정렬하는 실험을 크기마다 200번씩 돌렸어요.

뺄셈이 int 범위를 넘으면 부호가 뒤집혀 "a < b, b < c 인데 c < a" 같은 모순이 생겨요. 작은 목록에서는 예외 없이 순서만 틀리고, 큰 목록에서야 예외가 나요. 그래서 "단위 테스트는 통과했는데 운영에서 터진다"가 돼요. 값 범위를 0~10억으로 좁히면 뺄셈이 넘치지 않아 10만 건 200번 모두 정상이었지만, 데이터 범위는 언젠가 바뀌니 기대지 않아요.

예외를 만났을 때 확인 순서예요.

1. 비교 코드에서 a - b, (int)(x - y), Long 을 int 로 자른 반환을 찾아 Integer.compare·Long.compare·Comparator.comparingInt 로 바꿔요.
2. Double 비교는 Double.compare 로 바꿔요. <·> 로 직접 짜면 NaN 에서 규약이 깨져요.
3. 비교 안에서 난수, 현재 시각, 캐시 조회, 외부 호출을 쓰는지 봐요. 같은 두 값에 늘 같은 답을 내야 해요.
4. 정렬 중에 다른 스레드가 정렬 키 필드를 바꾸는지 봐요. 정렬 전에 키를 복사해 두면 사라져요.
5. if (a.x > b.x) return 1; return -1; 처럼 같을 때 0 을 안 돌려주는 분기를 찾아요. 같은 값이면 compare(a, b) 와 compare(b, a) 가 둘 다 -1 이 돼요.
6. 고친 뒤에는 32건 미만이 아니라 수만 건짜리 무작위 입력으로 다시 돌려요.

JDK-8072909 같은 구현 쪽 버그는 오래전에 고쳐졌으니, 지금 이 예외는 거의 항상 비교 함수 탓이에요.

정렬 결과가 이상할 때 확인 순서, 체크리스트

• 예외 메시지부터: 파이썬 '<' not supported between instances of 'str' and 'int' 는 타입이 섞인 거예요. list modified during sort 는 정렬 중에 그 리스트를 바꾼 거예요. 파이썬 문서는 정렬 중인 리스트가 비어 보이고, 수정을 알아채면 ValueError 를 낸다고 적어요.
• NaN: CPython 은 < 만 쓰는데 NaN 과의 비교는 늘 거짓이라 sorted([3.0, nan, 1.0, 2.0]) 가 입력 그대로 나와요. key=lambda x: (math.isnan(x), x) 로 NaN 을 맨 뒤로 보내면 [1.0, 2.0, 3.0, nan] 이 돼요.
• None·null: 파이썬은 None 과 숫자를 비교하면 TypeError, 자바는 Comparator.nullsLast(...) 로 감싸요.
• 숫자가 문자열: CSV·JSON 에서 읽은 값이 "10" 이면 "10" < "9" 예요. 초와 밀리초가 섞인 타임스탬프도 순서를 망가뜨려요(초·밀리초 혼동 버그 글).
• JS 기본 정렬: MDN Array.sort 문서대로 비교 함수가 없으면 문자열로 바꿔 UTF-16 코드 단위로 비교해요. Node 25 에서 [10, 9, 1, 100].sort() 는 [1, 10, 100, 9] 였어요.
• 사람이 읽는 순서: 코드값 정렬은 대문자가 소문자보다 앞이고 파일10 이 파일2 보다 앞이에요. 숫자를 수로 보는 자연 정렬은 JS 에서 Intl.Collator('ko', {numeric: true}) 로 되고, 목록 몇 개를 바로 확인할 땐 텍스트 줄 정렬기의 자연 정렬을 써도 돼요.

도입 전에 따질 것, 앱에서 정렬할까 DB 에서 할까

정렬을 코드에 넣기 전에 다섯 가지를 정해 두면 위 판단표가 대부분 정해져요.

• 어디서 정렬하나: 페이지마다 20건만 보여 준다면 DB 의 ORDER BY ... LIMIT 이 인덱스를 타서 앱으로 다 가져와 정렬하는 것보다 싸요. PostgreSQL ORDER BY 문서는 정렬 단계를 명시해야만 특정 순서가 보장된다고 적어요. 정렬 기준이 같은 행끼리의 순서도 정해 두려면 마지막에 고유 열(id)을 붙여요. 페이지를 넘길 때 같은 행이 두 번 나오는 버그가 여기서 생겨요.
• 얼마나 자주, 몇 건을: 조회마다 수만 건을 다시 정렬한다면 결과 캐시나 정렬된 저장을 먼저 봐요.
• 입력이 이미 얼마나 정렬돼 있나: 시간순 데이터면 정렬 비용이 거의 n 이라 걱정할 필요가 적어요. 무작위면 100만 건에서 이미 1초를 넘었어요.
• 같은 키의 순서가 의미 있나: 의미 있으면 안정 정렬(파이썬 리스트, 자바 객체, ES2019 이후 JS)만 써요. 자바 기본형 배열, DB 의 동점 행은 순서를 보장하지 않아요.
• 메모리 상한: key 정렬은 원소당 16바이트에 키 객체가 더해져요. 컨테이너 한도 안에서 n 을 넣어 계산해 둬요.

자주 묻는 질문

sorted() 와 list.sort() 중 어느 게 빠른가요?

정렬 자체는 같고, sorted() 는 새 리스트를 만드는 비용만 더해요. 100만 건에서 추가 메모리가 4MB 대 12MB 였어요. 원본이 필요 없으면 list.sort(), 원본을 지켜야 하거나 리스트가 아닌 반복 가능 객체면 sorted() 를 써요.

자바에서 Comparator 예외가 테스트에선 안 나요. 왜 그런가요?

32건 미만 목록은 병합 없이 삽입 정렬만 해서 규약 위반을 알아챌 자리가 없어요. 실험에서 31건 목록은 200번 중 191번 예외 없이 틀린 순서를 냈어요. 테스트에 수만 건 무작위 입력을 넣어야 드러나요.

파이썬에서 내림차순 + 오름차순을 섞으려면 cmp_to_key 가 필요한가요?

대부분 필요 없어요. 숫자 기준은 key=lambda r: (-r.score, r.name) 처럼 부호를 바꾸고, 문자열 기준이 섞이면 뒤 기준부터 reverse 를 바꿔 가며 여러 번 정렬해요. cmp_to_key 는 실측에서 8.6배 느렸어요.

parallelSort 를 항상 쓰면 더 빠르지 않나요?

8,192건 이하에서는 어차피 순차 정렬로 돌고, 큰 배열에서도 공용 ForkJoinPool 을 써서 서버의 다른 작업과 코어를 나눠요. 배치 작업처럼 코어가 남는 곳에서 큰 배열을 정렬할 때 써요.

정리

• 정렬 비용은 입력 모양이 정해요. 정렬된 100만 건 + 1천 건은 비교 103만 번, 무작위는 1,863만 번이었어요.
• 고르는 순서는 "앞쪽 몇 개만?(min·heapq) → 계속 추가?(모아서 한 번, 아니면 insort) → 자바 숫자?(int[]) → 기준 여러 개?(정수 키 또는 여러 번 정렬)"예요.
• 비교 함수보다 key 함수가 빠르지만, key 는 원소당 16바이트 + 키 객체만큼 메모리를 더 써요.
• 자바 비교는 Integer.compare·Comparator.comparing 계열만 쓰고, 테스트는 수만 건 무작위 입력으로 돌려요.

더 깊이 읽기

이 글은 실무에서 판단할 때 필요한 것 위주로 정리했어요. 같은 주제의 내부 동작 원리는 devboi 기술 블로그의 Timsort 원리 — 파이썬·자바 정렬의 런·갤로핑·powersort에서 도식과 코드로 단계별로 풀었어요.