短縮版：
値がわずかに変化するにもかかわらず、時間の経過とともにほぼ並べ替えられたデータをほぼ並べ替えられた順序で保持する手法を探しています。
シナリオは次のとおりです。
3Dグラフィックスの世界では、描画する前にオブジェクトを前から後ろに並べると便利なことがよくあります。シーンが変更されたり、シーンのビューが変更されたりすると、このデータは再並べ替えが必要になる場合がありますが、通常は並べ替えの順序に非常に近くなります（つまり、フレーム間であまり変化しません）。また、データが正確にソートされた順序であることが重要ではありません。発生する最悪の事態は、ポリゴンがレンダリングされてから完全に非表示になることです。これは小さなパフォーマンスヒットですが、世界の終わりではありません。
これを念頭に置いて、事前にデータを並べ替えてから、フレームごとに1回データに最小限のパッチを適用して、データがほとんど並べ替えられたままになるようにすることは可能ですか？このシナリオでは、ほとんどのオブジェクトが昇順である場合、データはほとんどソートされていると見なされます。つまり、適切な場所から10ステップ離れた1つのオブジェクトは、適切な場所から1ステップ離れた10個のオブジェクトよりもはるかに優れています（10倍優れています）。
また、データは通常1秒あたり30回（またはそれ以上）レンダリングされるため、データには半定期的にパッチが適用され続ける可能性があることにも注意してください。計算が効率的である限り、変更が停止してリストが完全にソートされるまで、時間をかけて計算を続けることができます。
既存のアイデア：
この問題に対する私のひざの反応は次のとおりです。
n log nデータがロードされたとき、および大きな変更（非常に簡単に追跡できます）にデータに並べ替えを適用します。データがゆっくりと変化し始めたら（たとえば、シーンが回転しているとき）、データにある種の単一の（線形）パスを適用して、後方に隣接するものをスワップし、ソート順を維持しようとします（これは基本的にシェルソートだと思います-多分あるかもしれませんこのシングルパスに使用するより良いアルゴリズム）。
変更が停止し、データが完全に並べ替えられるまで、各フレームの部分的な並べ替えを1回繰り返します。
手順2に戻り、さらに変更が加えられるのを待ちます。