-
Notifications
You must be signed in to change notification settings - Fork 1
/
sortlist.bdy
64 lines (55 loc) · 1.53 KB
/
sortlist.bdy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
Module: Sort Linked Lists
Author: dick@dickgrune.com (Dick Grune, Amstelveen)
Version: 2015-01-18
Description:
This is the implementation part of a generic routine that sorts
linked lists.
Instantiation:
See sortlist.spc
*/
#ifndef _SORT_EXTERN_DEFINED
static
#endif
void
SORT_NAME(struct SORT_STRUCT **l_hook) {
/* by split-sort-merge */
struct SORT_STRUCT *lst = *l_hook;
if (lst == 0) return; /* the empty list is sorted */
if (lst->SORT_NEXT == 0) return; /* a 1-element list is sorted */
/* There are at least two elements; split them into two sublists. */
struct SORT_STRUCT *q0 = 0, *q1 = 0; /* starts of the sublists */
struct SORT_STRUCT **q_hook[2]; /* append hooks for the lists */
q_hook[0] = &q0, q_hook[1] = &q1;
int q_cnt = 0; /* pertinemt sublist pointer */
while (lst) {
/* Detach the head element */
struct SORT_STRUCT *l = lst;
lst = lst->SORT_NEXT;
l->SORT_NEXT = 0;
/* and append it to the pertinent sublist. */
*q_hook[q_cnt] = l;
q_hook[q_cnt] = &l->SORT_NEXT;
q_cnt = 1 - q_cnt; /* switch pertinent sublist */
}
/* Sort recursively. */
SORT_NAME(&q0);
SORT_NAME(&q1);
/* Merge. */
*l_hook = 0;
while (q0 || q1) {
/* determine the list with the smallest head element */
struct SORT_STRUCT **h_hook = (
q0 == 0 ? &q1 :
q1 == 0 ? &q0 :
SORT_BEFORE((q0), (q1)) ? &q0 : &q1
);
/* detach head element */
struct SORT_STRUCT *l = *h_hook;
*h_hook = (*h_hook)->SORT_NEXT;
l->SORT_NEXT = 0;
/* append l to l_hook */
*l_hook = l;
l_hook = &l->SORT_NEXT;
}
}