クイックソートとは
配列の中から一つの要素を取り出し（ピボット）、その要素と比べて大きいか小さいかで残りの要素を別の配列に分ける。
この処理を分けた配列に対して、再帰的に呼び出し、それを繰り返すことでソートをするアルゴリズム。
例
以下のような配列を昇順でクイックソートする場合を例に挙げる。
arr = [10, 5, 2, 3, 8]
①まずはピボットとなる値を取り出す。ここでは5をピボットとして取り出す。
（基本的にはどれでもいい）
pivot = arr.pop(1) // 5をピボットとして取り出す
②このpivotと比べて大きい値をまとめた配列と、小さいまたは同じ値をまとめた配列を作成する。
less = [2, 3] // 5以下の配列
greater = [8, 10] // 5よりも大きい配列
➂ピボットを配列化し、配列を結合する。このときlessとgreaterに関しては、①②の処理を再帰的に呼び出す。
return quick_sort(less) + [pivot] + quick_sort(greater)
④このままだと、再帰的に呼び出す時に無限ループに入ってしまう。そのためループを抜けるための基本ケースをquick_sort(arr)の頭に実装する。
if arr < 2:
return arr // arrが空または、要素が一つしかない場合は処理をせず、そのまま返す。
これを繰り返して、再帰的に呼び出されなくなったらソートが完了する。
パフォーマンス
クイックソートのパフォーマンスは、選択するピボットによって変動する。
例えば下記のようなソート済み配列の、先頭をピボットとしてクイックソートをする場合。
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
lessとgreaterは下記のように、変化していく
// 一回目
pivot = 0
less = []
greater = [1, 2, 3, 4, 5, 6, 7, 8, 9]
// 二回目
pivot = 1
less = []
greater = [2, 3, 4, 5, 6, 7, 8, 9]
// 三回目
pivot = 2
less = []
greater = [3, 4, 5, 6, 7, 8, 9]
・
・
ソート済みの配列の先頭は、その配列における最小値になるためlessは常に空になる。
（つまり部分配列のが空）
そのた配列を二分するという考え方のクイックソートの強みが生かせていない。
この場合の計算量は各ループではO(N)となり、それが全要素行うためO(N2)となる。
そのためピボットは、中央値を3つとったものから選んだりして工夫する必要がある。
また再帰的に呼び出していく中で、配列の要素数が少なくなってきたら挿入ソートに切り替えるなどの実装がよく使われる。
例：V8エンジン
https://github.com/v8/v8/blob/master/src/js/array.js#L760-L844