JavaScript:クイックソートを末尾再帰にしてみる

クイックソートを末尾再帰にしようと思ったのだが、「あれ、これ無理じゃん」と思ったので調べてみた。
継続渡し、というものがあってそれを使うとできるらしい。

元記事：再帰クイックソートの可視化

詳しくは元記事を参照してください。
ここでは、アロー関数を使って今風にしてみたらどうなるか?をやってみます。

// 先頭の要素との大小で配列を二つに分割する関数
const divByHead = xs =>
  xs.slice(1).reduce(
    (acc,e)=>
      e <= xs[0] ? {...acc, le:[...acc.le, e]}
      : {...acc, gt:[...acc.gt, e]}
    , {le:[], gt:[]}
  )

// 末尾再帰でないクイックソート
const qs = xs =>{
  if(xs.length === 0) return []
  const divided = divByHead(xs)
  return  [...qs(divided.le), xs[0], ...qs(divided.gt)]
}

//継続渡しスタイルのクイックソート
const qs_cps = xs => k =>{
  if(xs.length === 0) return k([])
  const divided = divByHead(xs)
  return qs_cps(divided.le)(
    v1 => qs_cps(divided.gt)(
      v2 => k([...v1, xs[0], ...v2])
    )
  )
}

// 使いかた:
const qs2 = xs => qs_cps(xs)(v => v);
qs2([9,4,5,7,2,5,1]);   // [ 1, 2, 4, 5, 5, 7, 9 ]

qs([9,4,5,7,2,5,1]);    // [ 1, 2, 4, 5, 5, 7, 9 ]

できた!
どうしてうまくいくのか?説明はできないが、ふわっとは理解できたし、末尾再帰への変換もできそう。