次のシーケンスを取得しました(ツリーを表します):
4 2
1 4
3 4
5 4
2 7
0 7
6 0
ここで、値が左側 (列 1) に表示されたときに、右側 (列 2) に既に表示されているように、このシーケンスを並べ替えようとしています。より具体的には、並べ替えアルゴリズムの結果は次のようになります。
1 4
3 4
5 4
4 2
2 7
6 0
0 7
明らかに、これは O(n^2) で機能し、アルゴリズムは列 1 の各エントリを反復し、次に列 2 で対応するエントリを探します。しかし、私のシナリオでは n が非常に大きくなる可能性があるため (> 100000)、O(n log n) の方法を探しています。これは可能ですか？