Como ordenar uma lista de cordas?

Resposta básica:

mylist = ["b", "C", "A"]
mylist.sort()

Isto modifica a sua lista original (ou seja, tipos no local). Para obter uma cópia ordenada da lista, sem alterar o original, utilize a função sorted():

for x in sorted(mylist):
    print x

Entretanto, os exemplos acima são um pouco ingênuos, porque eles não levam em conta o locale't levam em conta o locale, e realizam uma classificação sensível a casos. Você pode tirar vantagem do parâmetro opcional key para especificar a ordem de ordenação personalizada (a alternativa, utilizando cmp, é uma solução depreciada, já que ela tem que ser avaliada várias vezes - key só é computada uma vez por elemento).

Então, para ordenar de acordo com o local atual, levando em conta as regras específicas do idioma (cmp_to_key é uma função de ajuda dos functools):

sorted(mylist, key=cmp_to_key(locale.strcoll))

E finalmente, se você precisar, você pode especificar um locale personalizado para a ordenação:

import locale
locale.setlocale(locale.LC_ALL, 'en_US.UTF-8') # vary depending on your lang/locale
assert sorted((u'Ab', u'ad', u'aa'),
  key=cmp_to_key(locale.strcoll)) == [u'aa', u'Ab', u'ad']

Última nota: você verá exemplos de ordenação não sensível a maiúsculas e minúsculas que utilizam o método lower() - esses são incorretos, porque funcionam apenas para o subconjunto de caracteres ASCII. Esses dois estão errados para qualquer dado não-inglês:

# this is incorrect!
mylist.sort(key=lambda x: x.lower())
# alternative notation, a bit faster, but still wrong
mylist.sort(key=str.lower)

list.sort()

É realmente assim tão simples :)

Mas como é que isto lida com as regras de classificação específicas da linguagem? Leva em conta o locale?

Não, list.sort() é uma função de ordenação genérica. Se você quiser ordenar de acordo com as regras Unicode, você'terá que definir uma função de chave de ordenação personalizada. Você pode tentar usar o módulo pyuca, mas eu não'não sei o quão completo ele é.