How Fast Can We Sort?Computer Science Level pending
The most basic sorting algorithms, such as Bubble Sort, run in \(O(n^2)\) time. Some more complicated ones, like Merge Sort, improve dramatically to \(O(n\log(n))\) time. Is it possible to create a sorting algorithm with worst-case runtime \(O(n)?\)
Bonus: If "yes", can you name one and/or create one? If "no", why not?