```/* nag_chain_sort (m01cuc) Example Program.
*
* Copyright 2014 Numerical Algorithms Group.
*
* Mark 4, 1996.
* Mark 5 revised, 1998.
* Mark 7 revised, 2001.
*
* Mark 8 revised, 2004
*
*/

#include <nag.h>
#include <stdio.h>
#include <nag_stdlib.h>
#include <nag_stddef.h>
#include <nagg05.h>
#include <nagm01.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;

/* Double scalars */
double      p;

/* NAG structures and types */
NagError    fail;
ptrdiff_t   ptroffset;
size_t      i, j, l;
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;

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

/* Get the length of the state array */
lstate = -1;
nag_rand_init_repeatable(genid, subid, seed, lseed, state, &lstate, &fail);
if (fail.code != NE_NOERROR)
{
printf("Error from nag_rand_init_repeatable (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;
}

/* Initialise the generator to a repeatable sequence */
nag_rand_init_repeatable(genid, subid, seed, lseed, state, &lstate, &fail);
if (fail.code != NE_NOERROR)
{
printf("Error from nag_rand_init_repeatable (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_discrete_uniform(1, (Integer) 0, (Integer) 5, state, draw,
&fail);
if (fail.code != NE_NOERROR)
{
printf(
"Error from nag_rand_discrete_uniform (g05tlc).\n%s\n",
fail.message);
exit_status = 1;
goto END;
}
vec[i].data = (double) draw;
}

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

/* 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;
base = &vec[l];

/* Print Input Data */
printf("nag_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("%10u%20ld%20.6f\n", i, vec[i].index, vec[i].data);
printf("   Matrix Index      Linked List Index      Data\n");
printf("%10u%20ld%20.6f\n",

/* Sort the linked list on the data field */
/* nag_chain_sort (m01cuc).
* Chain sort of linked list
*/
nag_chain_sort((Pointer *) &base, ptroffset, compare, Nag_Ascending, &fail);
if (fail.code != NE_NOERROR)
{
printf("Error from nag_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("%10u%20ld%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("%10u%20ld%20.6f\n",

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));
}
```