Timsort: un algoritmo de clasificación estable muy rápido, O (n log n), creado para el mundo real, no para fines académicos.
Timsort es un algoritmo de clasificación que es eficiente en datos reales, no creado en un laboratorio académico. Tim Peters creó Timsort para Python en 2001.
Timsort , , . Python, Java, Android GNU Octave.
Big O Timsort — O(n log n). Big O, .
Timsort , Mergesort, , . Timsort Mergesort. .
Peters Timsort , . "natural runs" ( ). , .
(array), , 64 , Timsort .
— , . , . :
,
, , [34, 10, 64, 51, 32, 21].
(sub-array), .
gif, :
64 , (pass) , . - , .
, , ( ):
, :
Minrun - , . , minrun. , 2. Timsort minrun, , , minrun 2.
minrun 32 64 , , 2.
minrun, minrun. .
, minrun 63, 33, : 63-33 = 30. 30 run[33], .
.
Timsort , . Timsort , .
. , . .
Timsort , . :
. , . .
Timsort . , , , , , , . " ", , .
, Timsort , :
1. A > B + C
2. B > C
A, B C - .
Tim Peters:
, , A, B C - .
. , . , Timsort . ( A B) .
Galloping*
*
Timsort A B, , "" . , A , B, A . c .
. Timsort , A , B, , , A , B.
Timsort galloping. A[0] B[0] , Timsort b[0] a[0]. , Timsort A. Timsort A[0] B. Timsort B.
. Timsort B[0] ( 5) , , A.
, B[0] A. Timsort A[0] ( 1) B. , , 1. B. , B A, A - B.
, , B[0] A ( ), gallop , . , Timsort gallop, "" A B. gallop , Timsort .
, Timsort :
, , .
, . .
Timsort , . Timsort C, Python.
Timsort Python, . Timsort, :
list.sort()
sorted(list)
, Timsort, , !
« ».
, .