Which order do you expect? What is your OS? Result on Linux (Fedora 21) with the french UTF-8 locale.

>>> locale.setlocale(locale.LC_ALL, '')
'fr_FR.utf8'
>>> locale.getlocale(locale.LC_COLLATE)
('fr_FR', 'UTF-8')
>>> sorted(x)
['Ά', 'Γ', 'Η', 'Κ', 'Ν', 'Ο', 'έ', 'ί', 'α', 'β', 'γ', 'δ', 'ε', 'ζ', 'ι', 'κ', 'λ', 'μ', 'ν', 'ο', 'ς', 'τ', 'φ', 'χ', 'ό', 'ϐ', 'Ἀ', 'ῖ']
>>> sorted(x, key=locale.strxfrm)
['Ἀ', 'ῖ', 'α', 'Ά', 'β', 'ϐ', 'Γ', 'γ', 'δ', 'ε', 'έ', 'ζ', 'Η', 'ι', 'ί', 'Κ', 'κ', 'λ', 'μ', 'Ν', 'ν', 'Ο', 'ο', 'ό', 'ς', 'τ', 'φ', 'χ']

I don't speak greek, I don't know which order is expected.

Anyway, as explained in the issue #23195, Python doesn't implement locale.strxfrm(): it just exposes the system functions. On Linux, locales are implemented in the GNU C library ("libc") for example.

So I don't see what should be done to "fix" this issue. We are not going to implement locales in Python, use an external library like ICU if you want "better" locales and have a better control on locales.