c++ - 拆分后维护二维点的排序数组（C++）

Question

到目前为止，我有一个二维点数组 (x_i, y_i)。在第一步中，我创建了一个按 x 坐标排序的数组和一个按 y 坐标排序的数组。然后我将 x 排序数组分成两半。我如何从这两半中重建 y 排序数组的相应两半，而无需再次按 y 坐标排序。似乎在线性时间内是可能的，而且应该很容易。谢谢。

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 排序”的排序顺序。