1 files changed, 82 insertions, 0 deletions
diff --git a/list_sort.c b/list_sort.c
new file mode 100644
index 0000000..6c6f54c
--- /dev/null
+++ b/list_sort.c
@@ -0,0 +1,82 @@
+/*
+ * Copyright 2001, 2002, 2003 David Mansfield and Cobite, Inc.
+ * See COPYING file for license information 
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "list_sort.h"
+
+void list_sort(struct list_head * list, int (*node_compare)(struct list_head *, struct list_head *))
+{
+    struct list_head *p, *q, *t;
+    struct list_head tmp;
+    int merges = 0;
+    int k = 1;
+    int psize, qsize; 
+
+    if (list_empty(list))
+	return;
+
+    do
+    {
+	INIT_LIST_HEAD(&tmp);
+	p = list->next;
+	merges = 0;
+	psize = qsize = 0;
+
+	while (p != list)
+	{
+	    merges++;
+	    q = p;
+
+	    while (q != list && psize < k)
+	    {
+		q = q->next;
+		psize++;
+	    }
+		
+	    qsize = k;
+
+	    while (psize || (qsize && q != list))
+	    {
+		if (psize && (qsize == 0 || q == list || node_compare(p, q) <= 0))
+		{
+		    t = p;
+		    p = p->next;
+		    psize--;
+		}
+		else if (qsize == 0)
+		{
+		    printf("whoaa. qsize is zero\n");
+		    exit (1);
+		}
+		else
+		{
+		    t = q;
+		    q = q->next;
+		    qsize--;
+		}
+		
+		list_del(t);
+		
+		list_add(t, tmp.prev);
+	    }
+
+	    p = q;
+	}
+
+	if (!list_empty(list))
+	{
+	    printf("whoaa. initial list not empty\n");
+	    exit (1);
+	}
+	    
+	list_splice(&tmp, list);
+	k *= 2;
+
+	//printf("done w sort pass %d %d\n", k, merges);
+    }
+    while (merges > 1);
+}
+