/* $Id$ */ /* * Copyright (c) 2009 Dimitri Sokolyuk * * 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 #include #include #include 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); k = 1; do { 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; lprint(">", list); k *= 2; } while (merges > 1); 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(int argc, char **argv) { List *head, **headp, *p, *next; int i, n; n = (argc == 2) ? atoi(argv[1]) : 13; head = NULL; headp = &head; srandom(time(NULL)); for (i = 0; i < n; i++) { *headp = malloc(sizeof(List)); assert(*headp); (*headp)->value = random() % n; 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; }