メモログ

💡 Personal notes about somthing I'm interested in

TypedArray.prototype.sort について

前回の「Array.prototype.sort について」に引き続き、今度はTypedArraysortについて。実装は別だけど対応は基本的に同じなので簡単に。

Chromeの実装はtyped-array.tqあたりで、Quicksortが使われている。compareFunctionがない場合は、TypedArraySortFastが実行され、この実行の内部ではC++のstd:sortが使われている。

Firefoxの実装はTypedArray.jsあたりで、Quicksortが使われている。merge sortではなくquicksortなのはおそらくTypedArrayは数値のみなのでstableであることを気にかける必要がないからだと思う(たぶん)。compareFunctionがない場合は、8ビット長の場合はCountingSort、16・32ビット長の場合はRadixSortが使われている。

Safariの実装はTypedArrayPrototype.jsあたりで、merge sortが使われている。compareFunctionがない場合は@typedArraySortが使われるのだけど、実装がどこにあるのか見つけられなかった。

Microsoft Edgeの実装はTypedArray.cppあたりで、Quicksortが使われている。

TypedArrayのsortでも同様にO(n log n)を期待できる。

以上。