1 /* $Id: llmosrt.c 21352 2006-03-19 18:18:15Z peterw $ */
2 /* A Linked-List Memory Sort
5 http://www.alumni.caltech.edu/~pje/
8 /* According to his website, this file was released into the public domain by Phillip J. Erdelsky */
13 void *sort_linked_list(void *p
, unsigned index
, int (*compare
)(void *, void *))
16 unsigned long block_size
;
20 struct record
*next
[1];
21 /* other members not directly accessed by this function */
26 struct record
*first
, *last
;
30 /* Distribute the records alternately to tape[0] and tape[1]. */
32 tape
[0].count
= tape
[1].count
= 0L;
37 struct record
*next
= ((struct record
*)p
)->next
[index
];
38 ((struct record
*)p
)->next
[index
] = tape
[base
].first
;
39 tape
[base
].first
= ((struct record
*)p
);
45 /* If the list is empty or contains only a single record, then */
46 /* tape[1].count == 0L and this part is vacuous. */
48 for (base
= 0, block_size
= 1L; tape
[base
+1].count
!= 0L;
49 base
^= 2, block_size
<<= 1)
52 struct tape
*tape0
, *tape1
;
54 tape1
= tape
+ base
+ 1;
56 tape
[dest
].count
= tape
[dest
+1].count
= 0;
57 for (; tape0
->count
!= 0; dest
^= 1)
60 struct tape
*output_tape
= tape
+ dest
;
64 struct record
*chosen_record
;
65 struct tape
*chosen_tape
;
66 if (n0
== 0 || tape0
->count
== 0)
68 if (n1
== 0 || tape1
->count
== 0)
73 else if (n1
== 0 || tape1
->count
== 0)
78 else if ((*compare
)(tape0
->first
, tape1
->first
) > 0)
89 chosen_record
= chosen_tape
->first
;
90 chosen_tape
->first
= chosen_record
->next
[index
];
91 if (output_tape
->count
== 0)
92 output_tape
->first
= chosen_record
;
94 output_tape
->last
->next
[index
] = chosen_record
;
95 output_tape
->last
= chosen_record
;
101 if (tape
[base
].count
> 1L)
102 tape
[base
].last
->next
[index
] = NULL
;
103 return tape
[base
].first
;