Tabasco Sort: a super-optimal merge sort

http://www.pvk.ca/Blog/2012/08/27/tabasco-sort-super-optimal-merge-sort

by dduck • 14 years ago

109 5 14 years ago

pvk.ca

throwaway54-762• 14 years ago

How does this compare with e.g. Timsort[0]?

[0] http://svn.python.org/projects/python/trunk/Objects/listsort...

psykotic• 14 years ago

What makes timsort fast is how it adapts to common patterns in the data (sorted runs, etc). Paul isn't trying to do any of that.

shabble• 14 years ago

As mentioned in the reddit thread[1], the occasional mentions of 'Python' refer to the SBCL compiler[2] rather than the little-p python language. This confused me for a little while as I tried to figure out how they were running on the python VM.

[1] http://www.reddit.com/r/programming/comments/yy6e4/tabasco_s...

[2] http://insidelisp.blogspot.co.uk/2010/04/book-chapter-11-wha...

badusername• 14 years ago

Can we amp up the creativity in naming these things? Coffeescript, Tabasco Sort, Sriracha UI, Bacon Reduce?!

recursive• 14 years ago

We may have miscalculated what optimal meant in the past, but by definition, it can't be super-optimal.

Tabasco Sort: a super-optimal merge sort

Related Stories