Gol*_*oss 2 sorting algorithm sse simd time-complexity
我正在尝试找到一种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 intructions从这个结构中受益,以分别对4个数组进行排序.
我尝试使用SIMD比较器(_mm_cmplt_ps例如)和掩码交换(_mm_blendv_ps例如)来制作传统排序算法的修改版本(快速排序,堆排序,合并排序等)但我总是遇到理论上出现的问题成为O(n?log(n))决策树中的步骤.因此,决定是否设置枢轴(快速排序)或者是否要将父项与其中一个子项交换(堆排序)对于所有整个4个组件同时是不正确的(并且因此,下一步 - 向右或向左 - 是不正确的).
现在我只有O(n²)方法工作.
有任何想法吗？