Timsort General-Percose 또는 Python-Secific입니까?

Question

Timsort는 적응적이고 안정적이며 자연스러운 Mergesort입니다. 그것은 많은 종류의 부분적으로 주문한 배열 (LG (n!) 비교가 필요하지 않고 N-1만큼 적은 비교)에서 초자연적 인 성능을 가지고 있지만, Python의 이전에 고도로 조정 된 샘플 소트 하이브리드만큼 빠른 것입니다.

당신은 본 적이 있습니다 Timsort Cpython 외부에서 사용하십니까? 의미가 있습니까?

Answer 1

그렇습니다. 일반적으로 Cpython 이외의 Timsort를 사용하는 것은 의미가 있습니다.

현재가 있습니다 진행중인 노력 Java의 "수정 된 병합 정렬"을 Timsort로 바꾸려면 초기 결과는 상당히 긍정적입니다.

Answer 2

알고리즘은 매우 일반적이지만 이점은 파이썬에 따라 다릅니다. 대부분의 분류 루틴과 달리, Python의 목록. 소트 (Timsort를 사용하는 것)는 일반적으로 비교가 많은 아이템을 교환하는 것보다 비싸거나 (항상 포인터 사본 세트) 추가 메모리를 할당하는 것보다 더 비쌉니다 (항상 포인터의 배열 일 뿐이며 오버 헤드는 모든 파이썬 작동의 평균 오버 헤드에 비해 작기 때문입니다.)

비슷한 제약을 받고 있다면 적합 할 수 있습니다. 그래도 비교가 실제로 비싸지 않은 다른 사례를 아직 보지 못했습니다 :-)

Answer 3

특히 친숙하지는 않지만 "스마트"Mergesorts는 광범위한 소프트웨어 세계에서 매우 일반적입니다.

의미가 있는지 여부는 정렬하는 내용과 비교의 상대적 비용과 메모리 할당에 따라 다릅니다. 추가 메모리의 최대 2*N 바이트가 필요한 종류는 메모리 제한된 환경에서는 좋은 선택이 아닙니다.

Answer 4

이제 대답했습니다 위키 백과: Timsort는 Android에서 복사 한 Java 7에서 사용됩니다.

Answer 5

Timsort는 현재 Android에 있습니다. http://www.kiwidoc.com/java/l/x/android/android/5/java.util/c/timsort

Answer 6

연결 한 설명은 완전히 일반적인 것 같습니다.