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

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: