In the C implementation, is Test::index required?

[lh3]

In the C implementation, the type is defined as typedef struct { int value, index; } Test. Is Test::index required or is it just for the testing purpose? If we are allowed to add an index field to the array, it is trivial to achieve stable sort with any sorting algorithms, by using a comparison function

#define stable_lt(a,b) ((a).value < (b).value || ((a).value==(b).value \
                        && (a).index<(b).index))

to break any ties, but this is not the true in-place stable sort.

[BonzaiThePenguin]

The index is only there so it has some way of verifying that the sort was stable. It's only used by the Verify function, not Sort.

[lh3]

Thanks. Make sense.