Oleg Zabluda's blog
Wednesday, April 25, 2012
 
Academic research on sorting algorithms typically assumes either random initial conditions (average complexity) or...
Academic research on sorting algorithms typically assumes either random initial conditions (average complexity) or worst case conditions. However in real world, the sequence is almost always non-random and have large ascending or descending sub-sequences. Worst case can happen if it is common (i.e. reverse order for quicksort) or due to DOS via Algorithmic Complexity Attack. Which brings us to

http://en.wikipedia.org/wiki/Timsort

"""
Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsets of the data that are already ordered, and uses the subsets to sort the data more efficiently. [...] Timsort has been Python's standard sorting algorithm since version 2.3. It is now also used to sort arrays in Java SE 7, and on the Android platform.
"""

Timsort has best case complexity of N, at the cost of requiring additional memory, as much as N/2 pointers for the random data.

References:
http://mail.python.org/pipermail/python-dev/2002-July/026837.html
http://svn.python.org/projects/python/trunk/Objects/listsort.txt
http://www.drmaciver.com/2010/01/understanding-timsort-1adaptive-mergesort/
http://en.wikipedia.org/wiki/Sorting_algorithm
http://en.wikipedia.org/wiki/Timsort

Labels:


- posted by Oleg Zabluda @ 6:11 PM | permalink | | | technorati | bloglines | feedster
| |

Home

Powered by Blogger