並列化可能なソートを理解する

概要

モチベーションは、並列動作可能なソートをWebGPUのComputeShaderで実装してみたいってところで
その先の展望として、GaussianSplattingのzソートに応用できないかと思っている

参考になりそうなソース

安定のedoさん
https://edom18.hateblo.jp/entry/2020/09/21/150416
この記事で参照されているkodaiさんの記事
https://qiita.com/kodai100/items/d1ddb3f86ba5dccccf9f
で参照されているgithub
https://github.com/hiroakioishi/UnityGPUBitonicSort?tab=readme-ov-file

ダイレクトにWGSLで実装している例もあった
https://zenn.dev/aadebdeb/articles/webgpu-bitonic-sort
祖のリポジトリ
https://github.com/aadebdeb/webgpu-bitonicsort

別の実装
https://github.com/hjlld/webgpu-bitonic-sort

wikipedia
https://ja.wikipedia.org/wiki/バイトニックソート

https://github.com/hjlld/webgpu-bitonic-sort
このリポジトリに関してはWebGPUの情報が古いのか、実行してもWGSLコードのエラーで実行できなかった

これもだな
https://qiita.com/aa_debdeb/items/908bce0699d55e4271b5

ob5vrさんのscrapbox
https://scrapbox.io/0b5vr/Bitonic_Sort

るっちょさんのピクセルソートがbitonicで実装されているらしい
https://x.com/ruccho_vector/status/1274348518426083330

edoさんの解説が一番丁寧そうな気がしてきた
https://edom18.hateblo.jp/entry/2020/09/21/150416

こちらを参考にbitonic sortの理解をしよう
いまのところ考えることがごっちゃになってて混乱してる
https://qiita.com/aa_debdeb/items/908bce0699d55e4271b5

もしかしたらradixソートのほうがマッチしているかもしれない
bitonicソートに比べて（工夫しなければ）整数や値の範囲がわかっているときしか使えない代わりに
要素数の2の累乗制限がない