"Cooperation is crucial for the remarkable evolutionary success of the human species. Not surprisingly, some individuals are willing to bare additional costs in order to punish defectors. Current models assume that, once set, the fine and cost of punishment do not change over time. Here we show that relaxing this assumption by allowing players to adapt their sanctioning efforts in dependence on the success of cooperation can explain both, the spontaneous emergence of punishment, as well as its ability to deter defectors and those unwilling to punish them with globally negligible investments. By means of phase diagrams and the analysis of emerging spatial patterns, we demonstrate that adaptive punishment promotes public cooperation either through the invigoration of spatial reciprocity, the prevention of the emergence of cyclic dominance, or through the provision of competitive advantages to those that sanction antisocial behavior. Presented results indicate that the process of self-organization significantly elevates the effectiveness of punishment, and they reveal new mechanisms by means of which this fascinating and widespread social behavior could have evolved."