We devise efficient gossip-based protocols for some fundamental distributed tasks. The protocols assume an $n$-node network supporting point-to-point communication, and in every round, each node exchanges information of size $O(\log n)$ bits with (at most) one other node. We first consider the \emph{renaming} problem, that is, to assign distinct IDs from a small ID space to all nodes of the network. We propose a renaming protocol that divides the ID space among nodes using a natural push or pull approach, achieving logarithmic round complexity with ID space $\{1,\dots,(1+\epsilon) n\}$, for any fixed $\epsilon >0$. A variant of this protocol solves the \emph{tight} renaming problem, where each node obtains a unique ID in $\{1,\dots,n\}$, in $O(\log^2 n)$ rounds. Next we study the following \emph{sorting} problem. Nodes have consecutive IDs 1 up to $n$, and they receive numerical values as inputs. They then have to exchange those inputs so that in the end the input of rank $k$ is located at the node with ID $k$. Jelasity and Kermarrec (2006) suggested a simple and natural protocol, where nodes exchange values with peers chosen uniformly at random, but it is not hard to see that this protocol requires $\Omega(n)$ rounds. We prove that the same protocol works in $O(\log^2 n)$ rounds if peers are chosen according to a non-uniform power law distribution.