Given a collection of red and blue mobile vehicles scattered across two discrete horizontal grid lanes, we seek to move all the blue vehicles to the far left-hand side and all the red vehicles to the far right-hand side, thus \textit{physically sorting} them according to color. The vehicles move simultaneously at discrete time steps $T=0, 1, \ldots$, and must not collide with each other. Our goal is to design a centralized algorithm that controls the vehicles so as to sort them in the least number of time steps. We find an optimal algorithm for this problem and prove its correctness. Furthermore, we derive an \textbf{exact} lower bound for the amount of time it takes to sort the vehicles given any staring configuration. Our sorting algorithm matches this lower bound, thus it is instance optimal, attaining the best possible sorting time for any initial configuration.
翻译:根据分散在两条离散的横向网格通道上的红色和蓝色机动车辆的集合情况,我们力求将所有蓝色车辆和所有红色车辆移到最左侧的极右侧,从而根据颜色对车辆进行物理排序。这些车辆在离散时间步骤同时移动 $T=0, 1,\ldots$, 并且不能相互碰撞。我们的目标是设计一种集中算法,控制车辆,以便以最少的时间步骤对车辆进行分类。我们为这一问题找到一种最佳算法,并证明其正确性。此外,我们为根据任何凝视配置对车辆进行排序所需的时间,得出了一种较低界限。我们的算法匹配了这个更低的界限,因此是最佳的,为任何初始配置取得最佳的排序时间。