Write a function group_games_by_genre(games) that receives a list of tuples, each tuple containing a game title (string) and its genre (string). The function should return a dictionary where each key is a genre and the corresponding value is a list of all titles belonging to that genre, sorted alphabetically. If the input list is empty, return an empty dictionary.
Example:
games = [("Zelda", "Adventure"), ("Mario", "Platformer"), ("Metroid", "Adventure"), ("Sonic", "Platformer")]
print(group_games_by_genre(games))
# {'Adventure': ['Metroid', 'Zelda'], 'Platformer': ['Mario', 'Sonic']}