最快的方式进行排序的条目的"平滑"2D阵列

Question

什么是最快的方式进行排序的价值在顺利2D阵?

输入是一个小过滤的形象：

• 约60 80素
• 单个信道
• 单人或双人精密浮
• 行主要储存、顺序在存储器
• 值已经混合的标志
• 分段"平滑"，与地区为10个象素宽

产出是一个平(约4800值)列的排序的价值，随着指数排序的原有阵列。

Answer 1

我敲定了一个快速和肮脏的基准某些的图像，使用顽固的种程序上的平面阵列。这是平均超过几百随机的图像和几百个像人的面孔。两者都是单的精确度。

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.

所有算法似乎受益于现有的部分排序，特别是快速排序.顽固，似乎没有一个排序的名单合并的功能，所以我不能试图预先排序排，唉。

Answer 2

我期望Timsort赢得这因为它需要利用"运行"在数据。

快速排序通常将要快，但是有风险的，你打了一个最糟糕的情况。例如某些版本的quickshort是O(n^2)当给已经排序的输入。这将不会是非常友好，如果有人给了你错误类型的梯度填充的图像。....

这是一个略有疯狂的想法的-你也可以尝试一Z排序通过(维基百科的链接 的)，这可以使你能够利用相邻的类似的色彩，在这两个方面。

Answer 3

我会开始与在地方快速排序.浮点比较快，在大多数处理(当然快得多于分配的需要成了归并排序).

Answer 4

有timsort，但我已经看到在几个地方，这意味着应用程序的缓慢进行比较;在顽固的开发者显然决定不甚至懒得执行它：

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

Answer 5

一个可能成了归并排序的行单独地，然后合并排序行。

这将至少利用一些特殊的结构2D阵列，即事实上，单调的运行将会通常开始，并停止在边缘阵列。它也暴露了另一对夫妇级别的并行性。