c++ - 分割後の2Dポイントのソートされた配列の維持（C ++）

Question

これまでのところ、2Dポイントの配列（x_i、y_i）があります。最初のステップでは、x座標で並べ替えられた配列とy座標で並べ替えられた配列を作成します。次に、xソートされた配列を2つに分割します。これらの2つの半分から、y座標で再度並べ替えることなく、対応するyで並べ替えられた配列の2つの半分を再構築するにはどうすればよいですか。線形時間で可能であり、非常に簡単なはずです。ありがとう。

Answer 1

擬似コードの場合：

for p in sorted-by-y
    if p is in first half of sorted-by-x
        add p to first half of sorted-by-y
    else
        add p to second half of sorted-by-y

各「ハーフセット」の最後にpを追加すると、「yでソート」のソート順が維持されます。