파이썬 정렬 성능 비교: sorted(), sort(), key=lambda 성능 차이는?

파이썬 정렬 성능 비교: sorted(), sort(), key=lambda 성능 차이는?

정렬은 모든 프로그래밍에서 중요한 역할을 합니다. 파이썬에서는 sorted()와 list.sort()를 이용해 간단하게 정렬할 수 있는데요,
사용 방식에 따라 성능 차이가 발생할 수 있습니다. 이 글에서는 실제로 다양한 방식의 정렬을 비교해보고, 어떤 상황에서 어떤 정렬 방법이 적합한지 살펴보겠습니다.

---

✅ 1. 정렬 함수 종류 정리

함수	특징
sorted(iterable)	원본을 변경하지 않음, 새 리스트 반환
list.sort()	리스트 객체 자체를 정렬, 반환값 없음 (in-place)
key=lambda x: ...	정렬 기준을 지정할 수 있음
reverse=True	내림차순 정렬

---

✅ 2. 실험 환경 설명

• Python 3.11 기준
• 리스트 길이: 1,000,000개의 랜덤 숫자
• 측정 도구: timeit

import random
import timeit

data = [random.randint(1, 1000000) for _ in range(1_000_000)]

---

✅ 3. 성능 비교 실험

3.1 sorted() vs list.sort()

# 복사해서 새 리스트 정렬
sorted_time = timeit.timeit("sorted(data)", globals=globals(), number=1)

# 리스트 자체를 정렬
copy_data = data.copy()
sort_time = timeit.timeit("copy_data.sort()", globals=globals(), number=1)

print(f"sorted(): {sorted_time:.4f}초")
print(f"list.sort(): {sort_time:.4f}초")

 

📌 결과 예시:

sorted(): 0.2712초
list.sort(): 0.2108초

list.sort()가 메모리를 덜 사용하므로 약간 더 빠름

---

3.2 key=lambda vs 함수 분리

# key=lambda 방식
lambda_time = timeit.timeit("sorted(data, key=lambda x: x % 100)", globals=globals(), number=1)

# 함수 분리
def mod100(x): return x % 100
func_time = timeit.timeit("sorted(data, key=mod100)", globals=globals(), number=1)

print(f"lambda: {lambda_time:.4f}초")
print(f"key function: {func_time:.4f}초")

 

📌 결과 예시:

lambda: 0.4001초
key function: 0.3507초

lambda는 간편하지만, 함수 호출 비용이 커지면 분리된 함수가 더 빠를 수 있음

반응형

---

3.3 정렬 전에 key를 캐싱하는 방식 (decorate-sort-undecorate 패턴)

# 느린 방식: 매번 key 함수 호출
slow = timeit.timeit("sorted(data, key=lambda x: x % 100)", globals=globals(), number=1)

# 빠른 방식: key를 먼저 계산
def fast_sort(data):
    decorated = [(x % 100, x) for x in data]
    decorated.sort()
    return [x[1] for x in decorated]

fast = timeit.timeit("fast_sort(data)", globals=globals(), number=1)

print(f"key=lambda: {slow:.4f}초")
print(f"decorated sort: {fast:.4f}초")

 

📌 결과 예시:

key=lambda: 0.4105초
decorated sort: 0.2901초

decorate-sort-undecorate 방식은 복잡한 key 함수가 반복 호출될 때 훨씬 빠릅니다

---

✅ 4. 상황별 추천 정렬 방식

상황	추천 방식
간단한 정렬	sorted(list) 또는 list.sort()
대용량 데이터 정렬	list.sort() + key function (함수 분리 권장)
정렬 기준이 복잡한 경우	decorate-sort-undecorate 방식
정렬 후 원본 유지해야 할 때	sorted(list) 사용

---

✅ 5. Timsort란?

파이썬의 sorted()와 sort()는 Timsort 알고리즘을 사용합니다.

이는 병합 정렬(Merge sort) + **삽입 정렬(Insertion sort)**의 하이브리드로,

최악 시간복잡도는 O(n log n), 정렬된 정도에 따라 **최선은 O(n)**까지도 나옵니다.

---

✅ 6. 최종 요약

• list.sort()는 더 빠르지만 원본이 변경됩니다.
• lambda는 편하지만 반복 호출이 많으면 느릴 수 있습니다.
• 복잡한 정렬 조건에서는 decorate-sort-undecorate 패턴이 효과적입니다.
• 파이썬은 내부적으로 매우 빠른 정렬 알고리즘(Timsort)을 사용합니다.