Python으로 모든 정렬 알고리즘을 구현했더니 — Python의 내장 정렬이 모두 압도했습니다

Source: Dev.to

벤치마크 결과

주요 요점

• Insertion sort는 매우 작은 입력에서 Merge/Quick보다 빠릅니다; 파이썬의 함수 호출은 비용이 많이 듭니다: 단일 CPU 명령이 아니라 메서드 디스패치와 타입 검사가 포함됩니다.
• 재귀 오버헤드 때문에 Quick sort의 함수 호출이 비싸집니다.
• 메모리 할당: Merge sort는 수천 개의 임시 리스트를 만들며, 이는 GC 일시 정지를 초래합니다.
• Timsort는 하이브리드 천재 알고리즘입니다: 연속된 구간을 감지하고, 작은 청크에는 삽입 정렬을 사용하며, 적응적으로 병합합니다. 모두 최적화된 C로 구현되어 있습니다.

삽입 정렬 예제

def insertion_sort(arr):
    """Return a sorted copy of *arr* using insertion sort."""
    arr = arr.copy()
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

프로덕션 파이썬에서는 절대 직접 정렬을 구현하지 마세요.
sorted() 혹은 list.sort()를 사용하세요 — 더 빠르고, 안정적이며, 검증된 구현입니다. 직접 구현하는 경우는 학습 목적이나 드문 특수 상황에만 제한하세요.

추가 자료

• 상세 설명 – (link to the full article)
• 전체 소스 코드 – (link to the repository)
• 벤치마크 스크립트 – (link to the script)
• 원시 벤치마크 데이터 – (link to the data)

외부 링크

• 전체 블로그 게시물:
• GitHub 저장소:

Python의 정렬 성능에서 가장 놀라웠던 점은 무엇인가요?
댓글에 자유롭게 의견을 남겨 주세요.