Hacker News new | past | comments | ask | show | jobs | submit login

> I would have guessed every possible iteration of sorting algorithms has been already explored, proven and tested

The search space is infinite, so exhaustively exploring it is impossible.






Nit: it's possible that there is a finite number of Pareto optimal sorting algorithms, and it may be possible to enumerate those.

Oh man if I could efficiently enumerate algorithms across the Pareto front of anything I’d be a happy camper.

Procedures that enumerate Turing machines are generally very easy, or nigh impossible


You'd probably want to start by defining equivalence and then work from there. If your criteria for equivalence is loose enough you're already done, e.g., if you just look at runtime big O for randomized arrays or something you can't do better than n lg n so there's just the one Pareto optimal choice, with many possible implementations.

It depends on your model of computation.

O(n log n) is only the frontier for comparison based sorts that know nothing about the distribution of inputs.

If your sorting algorithm is allowed to do anything else on your data, like hashing or looking at bits or arithmetic, different lower bounds might apply.




Applications are open for YC Summer 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: