Pythonのソートの基本

公式チュートリアルを見ると大変わかりやすくまとまっているが、最低限の特徴としては、

組み込み関数sorted()とリストのメソッドlist.sort()があるが仕組みや応用の仕方は同じ
キーワード引数keyにキー関数を設定することでいろいろなソートを実現できる

今回の目標

['aB', 'A', 'ab', 'AB', 'a', 'Ab', 'b', 'B']

が

['A', 'a', 'AB', 'Ab', 'aB', 'ab', 'B', 'b']

となるようなソートを目指す

よくある方法と問題点

普通にソート

>>> sorted(texts)
['A', 'AB', 'Ab', 'B', 'a', 'aB', 'ab', 'b']

今はほとんどの文字列がAかaから始まっているので違和感は少ないかもしれないが、Bがa aB abより早く並んでいるのが問題である
文字列のソートはUnicodeを元にしており、Unicode上ではアルファベット大文字がアルファベット小文字より先に来るからである（参考：式>比較>値の比較）

参考：アルファベット周辺のUnicode表

U+	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0040	@	A	B	C	D	E	F	G	H	I	J	H	I	J	K	L
0050	P	Q	R	S	T	U	V	W	X	Y	Z	[	\	]	^	_
0060	`	a	b	c	d	e	f	g	h	i	j	k	l	m	n	o
0070	p	q	r	s	t	u	v	w	x	y	z	{	\|	}	~	DEL

大文字小文字を揃えてソート

>>> # operator.methodcaller()も使えるが、今回はlambdaで大文字に揃えている
>>> sorted(texts, key=lambda t: t.upper())
['A', 'a', 'aB', 'ab', 'AB', 'Ab', 'b', 'B']

これでBがaより後ろに来て一見良さそうに見えるが、よく見てみると大文字と小文字の並びに統一感がない。例えば、Aとaでは大文字が先に来ているのに、Bとbでは小文字が先に来ている
それもそのはずで大文字や小文字に揃えているため、大文字と小文字を同じものとして扱ってしまうからである

解決策

タプルのようなシーケンスの比較では、最初の等価でない要素の順序と同じになるという性質がある（参考：式>比較>値の比較）
そのためタプルを返す関数をキー関数にすれば簡単に複数キーでのソートが実装できる

>>> sorted(texts, key=lambda t: (t.upper(), t))  # 大文字小文字を配慮したソート
['A', 'a', 'AB', 'Ab', 'aB', 'ab', 'B', 'b']

一行で書けており大変すっきりして見えるが、一見何をしているかわかりづらいのでコメント必須

終わりに

他にも

比較関数とfunctools.cmp_to_key()
collections.UserStringのサブクラスを作って特殊メソッド__lt__()を上書き
組み込み関数に頼らずソートを丸々（ちなみにPythonの組み込みのソートはティムソート）

といった方法でも解決はできるが、今回の方法が一番簡単に感じる