mergesort - 对“平滑”二维数组的条目进行排序的最快方法

Question

对平滑二维数组中的值进行排序的最快方法是什么？

输入是一个小的过滤图像：

• 约 60 x 80 像素
• 单通道
• 单精度或双精度浮点数
• 行主要存储，在内存中顺序
• 值有混合符号
• 分段“平滑”，区域宽度约为 10 像素

输出是已排序值的平面（大约 4800 个值）数组，以及对原始数组进行排序的索引。

Answer 1

我希望 Timsort 能够赢得这场比赛，因为它利用了数据中的“运行”。

快速排序通常会很快，但存在遇到最坏情况的风险。例如，当给定已经排序的输入时，某些版本的 quickshort 是 O(n^2)。如果有人给你错误类型的渐变填充图像，那将不是很友好......

这是一个有点疯狂的想法 - 您也可以尝试 Z 排序通行证（维基百科链接），它可以让您利用两个维度中相邻的相似颜色。

Answer 2

我将从就地快速排序开始。浮点比较在大多数处理器上都很快（肯定比合并排序所需的分配快很多）。

Answer 3

我在平面数组上使用 numpy 的排序例程在一些图像上敲定了一个快速而肮脏的基准。这是数百张随机图像和数百张人脸图像的平均值。两者都是单精度。

On random images...
quicksort took 0.000153 seconds per image.
mergesort took 0.000170 seconds per image.
heapsort took 0.000241 seconds per image.
On real images...
quicksort took 0.000136 seconds per image.
mergesort took 0.000143 seconds per image.
heapsort took 0.000230 seconds per image.

所有算法似乎都受益于现有的偏序，尤其是快速排序。Numpy 似乎没有排序列表合并功能，所以我不能尝试对行进行预排序，唉。

Answer 4

有 timsort，但我在几个地方看到它适用于比较慢的应用程序；numpy 开发人员显然决定不去实现它：

http://mail.scipy.org/pipermail/scipy-dev/2009-May/011929.html

Answer 5

可以单独对行进行合并排序，然后合并已排序的行。

这至少会利用二维数组的一些特殊结构，即单调运行通常会在数组边缘开始和停止。它还公开了另外几个级别的并行性。