Ordering a linked list

[yves-surrel]

To segment an image, I first use a scan kernel to get a list of contour pixels, which are not ordered along the contour but follow the scan logic (from top left to bottom right, row-wise). Each entry of this list is a struct with a field currentand a field next, which are the linear index of the pixel in the image and the linear index of the next pixel along the contour. E.g.

cl.Array([(  14662,   16710, 135, 5, 2, 1, 0., 0., 0., 0.),
       (  14663,   14662,   7, 6, 3, 0, 0., 0., 0., 0.),
       (  14664,   14663,   7, 6, 3, 0, 0., 0., 0., 0.), ...,
       (1993750, 1993751, 112, 2, 1, 0, 0., 0., 0., 0.),
       (1993751, 1993752, 112, 2, 1, 0, 0., 0., 0., 0.),
       (1993752, 1991704, 120, 1, 4, 2, 0., 0., 0., 0.)],
      dtype=[('current', '<i4'), ('next', '<i4'), ('pattern', 'u1'), ('correctionMask', 'u1'), ('increment', 'u1'), ('transition', 'u1'), ('delta_z', '<f4'), ('slopes_x', '<f4'), ('slopes_y', '<f4'), ('altitudeCorrection', '<f4')])

What would be the most efficient way to order that list, to make entries follow the contour in the right order? E.g.

cl.Array([(  14662,   16710, 135, 5, 2, 1, 4.2901491e-03, -3.9719365e-05, -0.00429015, -0.00425096),
       (  16710,   16709,   1, 5, 3, 0, 4.2620275e-05,  0.0000000e+00,  0.        , -0.0042345 ),
       (  16709,   16708,   3, 6, 3, 0, 4.6061374e-05,  0.0000000e+00, -0.00427266, -0.00427266),
       ...,
       (1593677, 1593676,   7, 6, 3, 0, 2.1132741e-03,  0.0000000e+00,  0.00043996,  0.00043996),
       (1593676, 1593675,   7, 6, 3, 0, 2.1199407e-03,  0.0000000e+00,  0.00043505,  0.00043505),
       (1593675, 1593674,   7, 6, 3, 0, 2.1266195e-03,  0.0000000e+00,  0.00043013,  0.00043013)],
      dtype=[('current', '<i4'), ('next', '<i4'), ('pattern', 'u1'), ('correctionMask', 'u1'), ('increment', 'u1'), ('transition', 'u1'), ('delta_z', '<f4'), ('slopes_x', '<f4'), ('slopes_y', '<f4'), ('altitudeCorrection', '<f4')])

The only solution I found is to do it sequentially in a single work item, which is awfully slow (as expected, but not that much): 40 ms for 10,000 pixels. What better?