My initial algorithm:
- Compare element 0 with every other element, keeping track of how many elements are less than it.
- Repeat for each element until an element that is greater than exactly (k-1) elements is found.
I assume this would take $O(n^2)$ in the worst case. Can a faster runtime be achieved without sorting the list?