sorting - table.sort はどのアルゴリズムを使用しますか?

Question

Lua のデフォルトでどのアルゴリズムが使用されているか興味table.sortがあります。これは、私が遭遇した他のソート アルゴリズムよりも遅いためです。table.sortまた、Luaは C のエンジンで記述されているのか、それとも Lua のライブラリにあるのかにも興味があります。

Answer 1

table.sort はどのアルゴリズムを使用しますか?

（少し上にスクロール）状態のコメントtablib.c

/*
** {======================================================
** Quicksort
** (based on `Algorithms in MODULA-3', Robert Sedgewick;
**  Addison-Wesley, 1993.)
** =======================================================
*/

私が提供したリンクでソースコードを読むことができます。

また、Lua の table.sort が C で Engine に記述されているのか、それとも Lua のライブラリにあるのかにも興味があります。

現時点では、Lua に直接付属するすべてのライブラリ ( io、table、math...) は C で記述されています。

Answer 2

内部的にtable.sortはクイックソートを使用し、C で記述されています。クイックソートは安定していないことに注意してください。少し驚いたことに、Lua は C をqsort()直接使用していませんでした。

パフォーマンスに関しては、どの言語とどのアルゴリズムと比較しているか、どのようなデータをテストしているかなど、さまざまな要因があるため、特定するのは困難です。