On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness