```/* nag_sort_chain_sort (m01cuc) Example Program.
*
* Copyright 2020 Numerical Algorithms Group.
*
* Mark 27.1, 2020.
*
*
*/

#include <nag.h>
#include <stdio.h>

struct recd {
double data;
struct recd *next;
Integer index;
};

#ifdef __cplusplus
extern "C" {
#endif
static Integer NAG_CALL compare(const Nag_Pointer a, const Nag_Pointer b);
#ifdef __cplusplus
}
#endif

int main(void) {
/* Integer scalar and array declarations */
Integer exit_status = 0;
Integer lstate;
Integer *state = 0, draw[1];

/* Double scalars */
double p[1];

/* NAG structures and types */
NagError fail;
ptrdiff_t ptroffset;
size_t i, j, l[20];
struct recd *address, *base, *origbase, *vec = 0;

/* Set the number of data fields */
size_t n = 10;

/* Choose the base generator */
Nag_BaseRNG genid = Nag_Basic;
Integer subid = 0;

/* Set the seed */
Integer seed[] = {1762543};
Integer lseed = 1;

/* Initialize the error structure */
INIT_FAIL(fail);

/* Get the length of the state array */
lstate = -1;
nag_rand_init_repeat(genid, subid, seed, lseed, state, &lstate, &fail);
if (fail.code != NE_NOERROR) {
printf("Error from nag_rand_init_repeat (g05kfc).\n%s\n", fail.message);
exit_status = 1;
goto END;
}

/* Allocate arrays */
if (!(vec = NAG_ALLOC(20, struct recd)) ||
!(state = NAG_ALLOC(lstate, Integer))) {
printf("Allocation failure\n");
exit_status = -1;
goto END;
}

/* Initialize the generator to a repeatable sequence */
nag_rand_init_repeat(genid, subid, seed, lseed, state, &lstate, &fail);
if (fail.code != NE_NOERROR) {
printf("Error from nag_rand_init_repeat (g05kfc).\n%s\n", fail.message);
exit_status = 1;
goto END;
}

ptroffset = (ptrdiff_t)(((char *)&(vec->next)) - ((char *)vec));

/* Set data field to random number between 0 and 5 */
for (i = 0; i < n; ++i) {
/* Generate a random integer from a uniform distribution */
nag_rand_int_uniform(1, (Integer)0, (Integer)5, state, draw, &fail);
if (fail.code != NE_NOERROR) {
printf("Error from nag_rand_int_uniform (g05tlc).\n%s\n", fail.message);
exit_status = 1;
goto END;
}
vec[i].data = (double)draw[0];
}

/* Randomly set index fields from 0 to 9 */
for (i = 0; i < n; ++i) {
/* Generate a random value from a uniform distribution */
nag_rand_dist_uniform01(1, state, p, &fail);
if (fail.code != NE_NOERROR) {
printf("Error from nag_rand_dist_uniform01 (g05sac).\n%s\n",
fail.message);
exit_status = 1;
goto END;
}
j = (int)((i + 1) * p[0]);

/* j is less than or equal to i */
(vec[i]).index = (vec[j]).index;
(vec[j]).index = i;
}

/* Set next pointers to make linked list in index field order */
for (i = 0; i < n; ++i)
l[(vec[i]).index] = i;
for (i = 0; i < n - 1; ++i)
vec[l[i]].next = &vec[l[i + 1]];
vec[l[n - 1]].next = NULL;

/* Get pointers to the start of the linked list (base) and the start
of the array (origbase) */
origbase = &vec[0];
base = &vec[l[0]];

/* Print Input Data */
printf("nag_sort_chain_sort (m01cuc) Example Program Results\n");
printf("\nDATA\n\n");
printf("Matrix Order:\n");
printf("   Matrix Index      Linked List Index      Data\n");
for (i = 0; i < n; ++i)
printf("%10" NAG_UFMT "%20" NAG_IFMT "%20.6f\n", i, vec[i].index,
vec[i].data);
printf("   Matrix Index      Linked List Index      Data\n");
printf("%10" NAG_UFMT "%20" NAG_IFMT "%20.6f\n", address - origbase,

/* Sort the linked list on the data field */
/* nag_sort_chain_sort (m01cuc).
* Chain sort of linked list
*/
nag_sort_chain_sort((Pointer *)&base, ptroffset, compare, Nag_Ascending,
&fail);
if (fail.code != NE_NOERROR) {
printf("Error from nag_sort_chain_sort (m01cuc).\n%s\n", fail.message);
exit_status = 1;
goto END;
}

/* Output results */
printf("\nRESULTS\n\n");

/* The order in the input matrix is unchanged */
printf("Matrix Order:\n");
printf("   Matrix Index      Linked List Index      Data\n");
for (i = 0; i < n; ++i)
printf("%10" NAG_UFMT "%20" NAG_IFMT "%20.6f\n", i, vec[i].index,
vec[i].data);

/* But the linked list pointers have been changed to reflect
the ascending sort on the data field */
printf("   Matrix Index      Linked List Index      Data\n");
printf("%10" NAG_UFMT "%20" NAG_IFMT "%20.6f\n", address - origbase,

END:
NAG_FREE(vec);
NAG_FREE(state);

return exit_status;
}

static Integer NAG_CALL compare(const Nag_Pointer a, const Nag_Pointer b) {
double x = ((struct recd *)a)->data;
double y = ((struct recd *)b)->data;
return (x < y ? -1 : (x == y ? 0 : 1));
}
```