summaryrefslogtreecommitdiff
path: root/lsort.c
blob: ef58cf258a4c7027a0ed01090a7c136649d0ade4 (plain)
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* $Id$ */
/*
 * Copyright (c) 2009 Dimitri Sokolyuk <demon@dim13.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct list List;

struct list {
	int     value;
	List	*link;
};

int	cmp(const List *, const List *);
List	*lsort(List *list, int (*compar)(const List *, const List *));
void	lprint(char *, List *);

int
cmp(const List *a, const List *b)
{
	assert(a && b);
	return a->value - b->value;
}

List *
lsort(List *list, int (*compar)(const List *, const List *))
{
	List	**listp, *p, *q, *ep, *eq;
	int     i, k, merges;

	assert(list && compar);

	for (k = 1;; k *= 2) {
		p = list;
		list = NULL;
		listp = &list;

		for (merges = 0; p; merges++) {
			ep = p;
			for (i = 0; ep && i < k; i++)
				ep = ep->link;
			eq = q = ep;
			for (i = 0; eq && i < k; i++)
				eq = eq->link;

			while (p != ep || q != eq) {
				if (p == ep && q != eq) {
					*listp = q;
					q = q->link;
				} else if (p != ep && q == eq) {
					*listp = p;
					p = p->link;
				} else if (p != ep && q != eq && compar(p, q) > 0) {
					*listp = q;
					q = q->link;
				} else {
					*listp = p;
					p = p->link;
				}
				listp = &(*listp)->link;
			}
			p = eq;
		}
		*listp = NULL;
		if (merges <= 1)
			break;
	}

	return list;
}

void
lprint(char *pre, List *p)
{
	assert(p);
	if (pre)
		printf("%s\t", pre);
	for (; p; p = p->link)
		printf("%3d", p->value);
	printf("\n");
}

int
main(void)
{
	List	*head, **headp, *p, *next;
	int     order[] = {6, 2, 8, 4, 11, 1, 12, 7, 3, 9, 5, 0, 10};
	int     i, n = sizeof(order) / sizeof(order[0]);

	head = NULL;
	headp = &head;

	for (i = 0; i < n; i++) {
		*headp = malloc(sizeof(List));
		assert(*headp);
		(*headp)->value = order[i];
		headp = &(*headp)->link;
	}
	*headp = NULL;

	lprint(">>>", head);
	head = lsort(head, cmp);
	lprint("<<<", head);

	for (p = head; p; p = next) {
		next = p->link;
		free(p);
	}

	return 0;
}