From 7e0f021a9aec35fd8e6725e87e3313b101d26f5e Mon Sep 17 00:00:00 2001
From: Tobias Klauser <tklauser@distanz.ch>
Date: Sun, 27 Jan 2008 11:37:44 +0100
Subject: Initial import (2.0.2-6)

---
 reference/C/CONTRIB/SNIP/ll_msort.c | 77 +++++++++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)
 create mode 100755 reference/C/CONTRIB/SNIP/ll_msort.c

(limited to 'reference/C/CONTRIB/SNIP/ll_msort.c')

diff --git a/reference/C/CONTRIB/SNIP/ll_msort.c b/reference/C/CONTRIB/SNIP/ll_msort.c
new file mode 100755
index 0000000..4f78cdf
--- /dev/null
+++ b/reference/C/CONTRIB/SNIP/ll_msort.c
@@ -0,0 +1,77 @@
+/*
+** Here's an example of how to sort a singly-linked list.  I think it
+** can be modified to sort a doubly-linked list, but it would get a bit
+** more complicated.  Note that this is a recursive method, but the
+** recursion depth is limited to be proportional to the base 2 log of
+** the length of the list, so it won't "run away" and blow the stack.
+**
+**  10/21/93 rdg  Fixed bug -- function was okay, but called incorrectly.
+*/
+
+/* linked list sort -- public domain by Ray Gardner  5/90 */
+
+#include <stdio.h>              /* for NULL definition */
+#include <string.h>
+
+typedef struct list_struct {
+   struct list_struct *next;
+   char *key;
+   /* other stuff */
+   } list;
+
+/* returns < 0 if *p sorts lower than *q */
+int keycmp (list *p, list *q)
+{
+      return strcmp(p->key, q->key);
+}
+
+/* merge 2 lists under dummy head item */
+list *lmerge (list *p, list *q)
+{
+      list *r, head;
+
+      for ( r = &head; p && q; )
+      {
+            if ( keycmp(p, q) < 0 )
+            {
+                  r = r->next = p;
+                  p = p->next;
+            }
+            else
+            {
+                  r = r->next = q;
+                  q = q->next;
+            }
+      }
+      r->next = (p ? p : q);
+      return head.next;
+}
+
+/* split list into 2 parts, sort each recursively, merge */
+list *lsort (list *p)
+{
+      list *q, *r;
+
+      if ( p )
+      {
+            q = p;
+            for ( r = q->next; r && (r = r->next) != NULL; r = r->next )
+                  q = q->next;
+            r = q->next;
+            q->next = NULL;
+            if ( r )
+                  p = lmerge(lsort(r), lsort(p));
+      }
+      return p;
+}
+
+main (void)
+{
+      list *listp;                 /* pointer to start of list */
+
+      /* first build unsorted list, then */
+
+      listp = lsort(listp);                                 /* rdg 10/93 */
+
+      return 0;
+}
-- 
cgit v1.2.3-54-g00ecf