I'm trying to understand this algorithm: arXiv:quant-ph/9607014 and I already have a problem on page 1, when they say that initializing the memory and "marking the elements $j$ such that $T[j]<T[y]$" can be achieved in $O(\log N)$ steps. How is checking every singe element and marking it run in less than $O(N)$ steps? And also: is this step meant to restrict the set of states to which we apply Grover's algorithm? Can we simply forget about some kets and run it on some others?
Well, the idea is simple. You have at first a superposition of N indexes where $N=2^n$. So basically you are doing your operations on $n $ qubits, so they are $\log_2(N)$ in complexity. The oracle used for marking the states is just called once and is applied on about $n $ qubits, which marks the states where the output of the oracle is 1 (the one whose values are greater in this case).
The last questions you asked, if you mean to apply it on a subset of states in the superposition (often because we have $N$ which is not a power of 2, it is possible indeed. You can keep the states and do your quantum search with an oracle that will not mark them.