我正在尝试找到一种 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²) 方法有效。
有什么想法吗？
最佳答案
听起来像是 sorting network是您提出的问题的答案，因为比较器的位置不依赖于数据。 Batcher's bitonic mergesort是 O(n log2 n)。
关于algorithm - 按组件排序多值 (SIMD) 数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30454766/