sorting - 小さな配列をソートして*コピーする必要がある場合の挿入ソート+コピーの代替

Question

2 つの配列 A と B を考えます。どちらも長さ N で、N はかなり小さいものです。A の要素を並べ替え、並べ替えた要素を B に格納したいと思います。

A でインプレース挿入ソートを実行し、ソートされた値を B に一括コピーするのはかなり簡単です。ただし、これは次の 2 つの利点を活用できません。

1. 使用可能なサイズ N のスクラッチ スペースがあり、
2. ソートされた値は、最終的に A ではなく B になる必要があります。

それらの1つ（または両方）を利用して、挿入ソート+コピーの単純なソリューションよりも優れたパフォーマンスを発揮する別のアプローチ（おそらく修正された挿入ソート？）を誰かが提案できますか？

Answer 1

何年も後にやってくるが、もし誰かがこれに出くわしたら、これが私の 2 セントだ。挿入ソートとマージソートのような場違いな高速ソートを組み合わせて使用​​すると、最小限の改善が得られる場合があります。

1. 配列を四分の一に分割し、挿入ソートを使用してソートします
2. 第 1 四半期と第 2 四半期をスクラッチ スペースにマージします。第 3 四半期と第 4 四半期も同じです。
3. 前半と後半をゼロからターゲット配列にマージします

繰り返しますが、これはおそらく現実世界の改善を最小限に抑えており、おそらく時期尚早の最適化のケースです。アプリケーションのベンチマークを行って、アルゴリズムのこの部分を本当に改善する必要があるかどうか、または他の最適化に時間を費やしたほうがよいかどうかを確認することをお勧めします。