http://www.drmaciver.com/2010/01/understanding-timsort-1adaptive-mergesort/
Very good and clear article about the ideas under Timsoft algorithm.
http://svn.python.org/projects/python/trunk/Objects/listsort.txt
Original Tim Peterson description of the proposed algorithm and its evaluation.
http://warp.povusers.org/SortComparison/
Good and colorful comparison of standard sort algorithms (without optimization) but does not include Timsort.
Minus of the algorithm is that it uses O(n) space while normal merge sort algorithm uses only O(ln(n)) additional space in the stack (because it uses recursion). May be unsatisfying with really big N.
Very good and clear article about the ideas under Timsoft algorithm.
http://svn.python.org/projects/python/trunk/Objects/listsort.txt
Original Tim Peterson description of the proposed algorithm and its evaluation.
http://warp.povusers.org/SortComparison/
Good and colorful comparison of standard sort algorithms (without optimization) but does not include Timsort.
Minus of the algorithm is that it uses O(n) space while normal merge sort algorithm uses only O(ln(n)) additional space in the stack (because it uses recursion). May be unsatisfying with really big N.
No comments:
Post a Comment