2 * A Linked-List Memory Sort
3 * by Philip J. Erdelsky
6 * http://alumnus.caltech.edu/~pje/
9 * http://alumnus.caltech.edu/~pje/cdmake.txt
11 * An extended version can be found at:
12 * http://alumnus.caltech.edu/~pje/llmsort.html
13 * http://www.efgh.com/software/llmsort.htm
15 * Public domain; no restrictions on use.
20 void *sort_linked_list(void *p
, unsigned index
, int (*compare
)(void *, void *))
23 unsigned long block_size
;
27 struct record
*next
[1];
28 /* other members not directly accessed by this function */
33 struct record
*first
, *last
;
37 /* Distribute the records alternately to tape[0] and tape[1]. */
39 tape
[0].count
= tape
[1].count
= 0L;
44 struct record
*next
= ((struct record
*)p
)->next
[index
];
45 ((struct record
*)p
)->next
[index
] = tape
[base
].first
;
46 tape
[base
].first
= ((struct record
*)p
);
52 /* If the list is empty or contains only a single record, then */
53 /* tape[1].count == 0L and this part is vacuous. */
55 for (base
= 0, block_size
= 1L; tape
[base
+1].count
!= 0L;
56 base
^= 2, block_size
<<= 1)
59 struct tape
*tape0
, *tape1
;
61 tape1
= tape
+ base
+ 1;
63 tape
[dest
].count
= tape
[dest
+1].count
= 0;
64 for (; tape0
->count
!= 0; dest
^= 1)
67 struct tape
*output_tape
= tape
+ dest
;
71 struct record
*chosen_record
;
72 struct tape
*chosen_tape
;
73 if (n0
== 0 || tape0
->count
== 0)
75 if (n1
== 0 || tape1
->count
== 0)
80 else if (n1
== 0 || tape1
->count
== 0)
85 else if ((*compare
)(tape0
->first
, tape1
->first
) > 0)
96 chosen_record
= chosen_tape
->first
;
97 chosen_tape
->first
= chosen_record
->next
[index
];
98 if (output_tape
->count
== 0)
99 output_tape
->first
= chosen_record
;
101 output_tape
->last
->next
[index
] = chosen_record
;
102 output_tape
->last
= chosen_record
;
103 output_tape
->count
++;
108 if (tape
[base
].count
> 1L)
109 tape
[base
].last
->next
[index
] = NULL
;
110 return tape
[base
].first
;