This means mostly sorting by key:

for f in sorted(glob.glob('*.yml')) + sorted(glob.glob('[a-z]*/*.yml')):
    print(f)
    with open(f) as fp:
        data = yaml.safe_load(fp)
    with open(f, 'w') as fp:
        yaml.dump(data, fp, default_flow_style=False, sort_keys=True, allow_unicode=True)