arXiv:1406.1077cs.DS
How inefficient can a sort algorithm be?
Abstract
We find large lower bounds for a certain family of algorithms, and prove that such bounds are limited only by natural computability arguments.
On Hacker News
Linked by 2 identifiable commenters in 2 comments across 2 threads, from Jun 2016 to Oct 2021. Found in 1 HN submission from Jun 2016 to Jun 2016. Open submission discussions.
Discussed in comments2 threads
-
-
Direct link to paper: https://arxiv.org/pdf/1406.1077v1
-
Submitted to Hacker News
Also discussed alongside
Connected through shared HN threads, not inferred similarity or a recommendation.
Bogosort is pretty simple, too. while not is_sorted(a) do shuffle(a) However the shuffle function hides a surprising amount of complexity. It is nontrivial to write a correct shuffle function. [1] But Bogosort isn't even the worst sorting algorithm out there! There is also…
antogniniView on HNParent context