Sorting large vector by distance Lots of dating apps sort they results by distance. That's it, you're at position $(x, y)$ at the Earth map and the application shows you up to, let's say, $k$ potential partner. Those are not any people, but the $k$-nearest to you.
If I've got a vector $v$ with $n$ pairs $(x_i, y_i)$ indicating people's position, calculating the distance from my position $(x, y)$ to each position $(x_i, y_i)$ would be $\Theta(n)$, and selecting the $k$ smallest would probably be also $\Theta(n)$ (in mean in running time, probably using min heaps or something alike).
The problem is that $n$ may be huge (imagine how many users do use Tinder, Grindr and applications like that).
So, my question is, how do they do it so fast?

One data structure very applicable to this kind of problem is the k-d tree. (I think the wiki article explains it well enough, but comment if you have questions). If you store your positional data in a k-d tree, a nearest neighbor search becomes $O(\log(n))$.
I'm not sure if this is precisely what dating apps use (they probably just cluster by city where $n_{\text{city}}$ is "small enough" to brute search), but k-d trees are common in the field of motion-planning.
