Radix Sort Implementation is not Stable

[christian-lanius]

Hi, Thank you for providing these implementations! According to the internet, radix sort should be a stable sorting algorithm. However looking at a testcase, the results seem to be not stable. A simple example program to validate this:

typedef struct { uint64_t x, y; } mm128_t;
#include "ksort.h"
#define sort_key_128x(a) ((a).x)
KRADIX_SORT_INIT(128x, mm128_t, sort_key_128x, 8)
void main() {
    int n_z = 200;

    mm128_t *z = (mm128_t *) malloc(sizeof(mm128_t)*n_z);
    int j;
    for (j=0; j<n_z; j++){
        z[j].x = j%10;
        z[j].y = j;
    }

    mm128_t *cpubuff = (mm128_t *) malloc(sizeof(mm128_t)*n_z);
    memcpy((void *) cpubuff, (void *) z, sizeof(mm128_t)*n_z);

    radix_sort_128x(cpubuff, cpubuff+n_z);

    for (j=0; j<n_z; j++){
        printf("%3d \t %4lu %4lu\t\t %4lu %4lu\n", j, z[j].x, z[j].y, cpubuff[j].x,cpubuff[j].y);
    }

    free(cpubuff);
    free(z);

}

In the input sequence, the y value for x=0 is 0,10,20, etc (in that order). Thus, for a stable sorting implementation, the y value should stay in that order, i.e. the output of the program should be

  0         0    0                  0    0
  1         1    1                  0   10
  2         2    2                  0   20
  3         3    3                  0   30
  4         4    4                  0   40
  5         5    5                  0   50
  6         6    6                  0   60
  7         7    7                  0   70
  8         8    8                  0   80
  9         9    9                  0   90
 10         0   10                  0  100
 11         1   11                  0  110
 12         2   12                  0  120
 13         3   13                  0  130
 14         4   14                  0  140
 15         5   15                  0  150
 16         6   16                  0  160
 17         7   17                  0  170
 18         8   18                  0  180
 19         9   19                  0  190

But the actual programs output is

  0         0    0                  0    0
  1         1    1                  0   20
  2         2    2                  0   40
  3         3    3                  0   60
  4         4    4                  0   80
  5         5    5                  0  100
  6         6    6                  0  120
  7         7    7                  0  140
  8         8    8                  0  160
  9         9    9                  0  180
 10         0   10                  0   10
 11         1   11                  0   30
 12         2   12                  0   50
 13         3   13                  0   70
 14         4   14                  0   90
 15         5   15                  0  110
 16         6   16                  0  130
 17         7   17                  0  150
 18         8   18                  0  170
 19         9   19                  0  190

(I have omitted the rest of the output, it follows the same pattern).

I am not too comfortable with the actual code, so I can't propose a fix to this at this time.

Kind regards Christian

[attractivechaos]

In-place radix sort is unstable.

[christian-lanius]

Thank you very much for the fast response!