algorithm - 按分量排序多值 (SIMD) 数组

Question

我正在尝试找到一种 O(n∙log(n)) 排序方法来同时对多个数组进行排序，以便多值数组中的元素将代表来自 4 个不同的单个元素值数组和排序方法将对多值元素进行排序。

例如:
对于给定的 4 个单值数组 An、Bn、Cn 和 Dn，我会设置一个新数组 Qn
所以 Qᵢ = [ Aᵢ Bᵢ Cᵢ Dᵢ ]。
Qᵢ 可能会在此过程中发生变化，因此 Qᵢ = [ Aaᵢ Bbᵢ Ccᵢ Ddᵢ ]
其中aᵢ、bᵢ、cᵢ和dᵢ是索引列表
当然 Qᵢ ≤ Qᵢ₊₁ = [ Aaᵢ₊₁ Bbᵢ₊₁ Ccᵢ₊₁ Ddᵢ₊₁ ] 使得 Aaᵢ ≤ Aaᵢ₊₁, Bbᵢ ≤ Bbᵢ₊₁ 等等。其动机当然是使用 SIMD 指令以从这种结构中获益，以分别对 4 个数组进行排序。

我尝试使用 SIMD 比较器(例如 _mm_cmplt_ps)和屏蔽交换(例如 _mm_blendv_ps)制作传统排序算法的修改版本(快速排序、堆排序、归并排序等)但我总是遇到这样的问题，即理论上决策树中似乎有 O(n∙log(n)) 个步骤。因此，一个决定，是否设置一个枢轴(快速排序)或是否将父项与其子项之一交换(堆排序)对于所有 4 个组件同时在一起是不正确的(因此，下一步 - 向右或向左 - 是不正确的)。

现在我只有 O(n²) 方法在工作。

有什么想法吗？

Answer 1

听起来好像是 sorting network是您所问问题的答案，因为比较器的位置与数据无关。 Batcher's bitonic mergesort是 O(n log² n)。