単連結リストの整列 #57 最良時間計算量

最近、リストの実装特異的な話題ばかりだったので、本来の題目の整列関係について。
整列関数listsortは隣接交換法を使ってリストの要素を整列している。
隣接交換法ではリストの要素を要素数個回走査するため要素数の二次オーダの平均時間計算量になるが、
そのうちの一回の走査で一度も要素の交換を行わずに済んだ場合、それ以降の走査は必要なくなるため、
一回の走査で交換が一度でも行われたかどうかを覚えておくことで、
最良時間計算量は要素数の一次オーダで済むようになる。
これは整列処理前に既に整列状態になっている時の時間計算量である。
ただし、そのための新たな処理分のオーバーヘッドも加わることになる。