自分的に実装時にコードを思い浮かべやすいような表現を心がけました(無印良品ぽい言い回し)。
けんちょんさんの網羅的記事を読みながら書きました。それぞれのソートアルゴリズムの原理と実装を知っている人向けです。
O(N^2)
挿入ソート
左から順に1枚抜いて、それより左にあってかつ抜いたものより小さいものを右にずらすと、未ソート部の左端が空くのでそこに入れる。
選択ソート
線形探索して最小値と未ソート部の左端を交換していく。
バブルソート
右端から2つずつ比較して入れ替えを繰り返すと未ソート部の最小値が泡のように左端に移動する。
O(N log N)
マージソート
要素数が1になるまで再帰的に2分割して、つなげるときに左右から1個ずつ取り出して小さい方を突っ込む。
クイックソート
Pivot を選んで線形探索、pivot 未満を見つけたら左端に詰めて(交換して)いくと、pivot 未満と以上に分かれるので、pivot をふさわしい場所に入れてやり、あとは再帰的にやる。
ヒープソート
配列にヒープを埋め込んで、最大値を右端に飛ばしてヒープのサイズを小さくしていく。