Ternary sorting

[This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

The last Le Monde puzzle made me wonder about the ternary version of the sorting algorithms, which all seem to be binary (compare x and y, then…). The problem is, given (only) a blackbox procedure that returns the relative order of three arbitrary numbers, how many steps are necessary to sort a series of n nnumbers? The heapsort entry in Wikipedia mentions a ternary sorting version, but does not get into details. Robert Sedgewick (author of a fabulous book on algorithmic I enjoyed very much when I started programming) has a talk about the optimality of quicksort where he mentions ternary sorting, but this seems to be more related with ties than with my problem… It is of course highly formal in that I do not know of a physical device that would justify moving from binary to ternary comparisons.


Filed under: R Tagged: heapsort, Le Monde, quicksort, rank, sorting, wikipedia

To leave a comment for the author, please follow the link and comment on their blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.