Tabasco Sort: a super-optimal merge sort

Posted by dduck on Wednesday August 29, 2012 @02:21PM
from the pvk.ca dept.

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

( 5 comments | 109 points | on HN )

Re:Tabasco Sort: a super-optimal merge sort by shabble on Wednesday August 29, 2012 @03:09PM (#4450467)

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...

[ Parent | on HN ]

Re:Tabasco Sort: a super-optimal merge sort by throwaway54-762 on Wednesday August 29, 2012 @03:03PM (#4450436)

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

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

[ Parent | on HN ]

Re:Tabasco Sort: a super-optimal merge sort by psykotic on Wednesday August 29, 2012 @03:05PM (#4450443)

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.

[ Parent | on HN ]

Re:Tabasco Sort: a super-optimal merge sort by recursive on Wednesday August 29, 2012 @08:30PM (#4452233)

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

[ Parent | on HN ]

Re:Tabasco Sort: a super-optimal merge sort by badusername on Wednesday August 29, 2012 @08:26PM (#4452213)

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

[ Parent | on HN ]