Search code examples
mergesorttimsort

fastest way to sort the entries of a "smooth" 2D array

What is the fastest way to sort the values in a smooth 2D array?

The input is a small filtered image:

  • about 60 by 80 pixels
  • single channel
  • single or double precision float
  • row major storage, sequential in memory
  • values have mixed sign
  • piecewise "smooth", with regions on the order of 10 pixels wide

Output is a flat (about 4800 value) array of the sorted values, along with the indices that sort the original array.

Solution

  • I hammered out a quick and dirty benchmark on some images using numpy's sort routines on the flat array. This is averaged over a few hundred random images and a few hundred images of human faces. Both are single precision.

    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.

    All of the algorithms seem to benefit from the existing partial ordering, especially quicksort. Numpy doesn't seem to have a sorted list merge function, so I can't try pre-sorting the rows, alas.