# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1345113383 -7200
# Node ID ec296899d12f5c464d69f0887a58f88a838afaa9
# Parent  a9d656e4f7cec0477dca924f821e8d60e750cce2
replaced qsort with natural merge sort

diff -r a9d656e4f7ce -r ec296899d12f ucx/dlist.c
--- a/ucx/dlist.c	Thu Aug 16 11:31:16 2012 +0200
+++ b/ucx/dlist.c	Thu Aug 16 12:36:23 2012 +0200
@@ -112,64 +112,94 @@
     return s;
 }
 
-int ucx_dlist_qsort_devide(UcxDlist** list, int l, int r, cmp_func f, void* d) {
-    int i = l;
-    int j = r - 1;
-    void *p = list[r]->data;
-    UcxDlist *b;
+UcxDlist *ucx_dlist_sort_merge(int length,
+        UcxDlist* ls, UcxDlist* rs, UcxDlist* le, UcxDlist* re,
+        cmp_func fnc, void* data) {
+    UcxDlist *sorted[length];
+    UcxDlist *rc, *lc;
 
-    do {
-        while (i < r && f(list[i]->data, p, d) <= 0) i++;
-        while (j > l && f(list[j]->data, p, d) >= 0) j--;
-        if (i < j) {
-            b = list[i];
-            list[i] = list[j];
-            list[j] = b;
+    lc = ls; rc = rs;
+    int n = 0;
+    while (lc != le && rc != re) {
+        if (fnc(lc->data, rc->data, data) <= 0) {
+            sorted[n] = lc;
+            lc = lc->next;
+        } else {
+            sorted[n] = rc;
+            rc = rc->next;
         }
-    } while (i < j);
-
-    if (f(list[i]->data, p, d) > 0) {
-        b = list[r];
-        list[r] = list[i];
-        list[i] = b;
+        n++;
+    }
+    while (lc != le) {
+        sorted[n] = lc;
+        lc = lc->next;
+        n++;
+    }
+    while (rc != re) {
+        sorted[n] = rc;
+        rc = rc->next;
+        n++;
     }
 
-    return i;
-}
+    // Update pointer
+    sorted[0]->prev = NULL;
+    for (int i = 0 ; i < length-1 ; i++) {
+        sorted[i]->next = sorted[i+1];
+        sorted[i+1]->prev = sorted[i];
+    }
+    sorted[length-1]->next = NULL;
 
-void ucx_dlist_qsort_sort(UcxDlist** list, int l, int r, cmp_func f, void* d) {
-    if (l < r) {
-        int m = ucx_dlist_qsort_devide(list, l, r, f, d);
-        ucx_dlist_qsort_sort(list, l, m-1, f, d);
-        ucx_dlist_qsort_sort(list, m+1, r, f, d);
-    }
+    return sorted[0];
 }
 
 UcxDlist *ucx_dlist_sort(UcxDlist *l, cmp_func fnc, void *data) {
     if (l == NULL) {
         return NULL;
     }
-    size_t n = ucx_dlist_size(l);
-    if (n == 1) {
+
+    UcxDlist *lc;
+    int ln = 1;
+
+    UcxDlist *ls = l, *le;
+    lc = ls;
+    while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
+        lc = lc->next;
+        ln++;
+    }
+    le = lc->next;
+
+    UcxDlist *rs = le, *re;
+    if (rs == NULL) {
+        return l; // this list is already sorted :)
+    } else {
+        UcxDlist *rc;
+        int rn = 1;
+        rc = rs;
+        while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
+            rc = rc->next;
+            rn++;
+        }
+        re = rc->next;
+
+        // Something left? Sort it!
+        UcxDlist *remainder = re;
+        size_t remainder_length = ucx_dlist_size(remainder);
+        if (remainder != NULL) {
+            remainder = ucx_dlist_sort(remainder, fnc, data);
+        }
+
+        // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
+        UcxDlist *sorted = ucx_dlist_sort_merge(ln+rn,
+                ls, rs, le, re,
+                fnc, data);
+
+        // merge sorted list with (also sorted) remainder
+        l = ucx_dlist_sort_merge(ln+rn+remainder_length,
+                sorted, remainder, NULL, NULL,
+                fnc, data);
+
         return l;
     }
-
-    UcxDlist *entries[n];
-    entries[0] = l;
-    for (int i = 1 ; i < n ; i++) {
-      entries[i] = entries[i-1]->next;
-    }
-
-    ucx_dlist_qsort_sort(entries, 0, n-1, fnc, data);
-
-    entries[0]->prev = NULL;
-    for (int i = 0 ; i < n-1 ; i++) {
-      entries[i]->next = entries[i+1];
-      entries[i+1]->prev = entries[i];
-    }
-    entries[n-1]->next = NULL;
-
-    return entries[0];
 }
 
 /* dlist specific functions */
diff -r a9d656e4f7ce -r ec296899d12f ucx/list.c
--- a/ucx/list.c	Thu Aug 16 11:31:16 2012 +0200
+++ b/ucx/list.c	Thu Aug 16 12:36:23 2012 +0200
@@ -108,62 +108,92 @@
     return s;
 }
 
-int ucx_list_qsort_devide(UcxList** list, int l, int r, cmp_func f, void* d) {
-    int i = l;
-    int j = r - 1;
-    void *p = list[r]->data;
-    UcxList *b;
+UcxList *ucx_list_sort_merge(int length,
+        UcxList* ls, UcxList* rs, UcxList* le, UcxList* re,
+        cmp_func fnc, void* data) {
+    UcxList *sorted[length];
+    UcxList *rc, *lc;
 
-    do {
-        while (i < r && f(list[i]->data, p, d) <= 0) i++;
-        while (j > l && f(list[j]->data, p, d) >= 0) j--;
-        if (i < j) {
-            b = list[i];
-            list[i] = list[j];
-            list[j] = b;
+    lc = ls; rc = rs;
+    int n = 0;
+    while (lc != le && rc != re) {
+        if (fnc(lc->data, rc->data, data) <= 0) {
+            sorted[n] = lc;
+            lc = lc->next;
+        } else {
+            sorted[n] = rc;
+            rc = rc->next;
         }
-    } while (i < j);
-
-    if (f(list[i]->data, p, d) > 0) {
-        b = list[r];
-        list[r] = list[i];
-        list[i] = b;
+        n++;
+    }
+    while (lc != le) {
+        sorted[n] = lc;
+        lc = lc->next;
+        n++;
+    }
+    while (rc != re) {
+        sorted[n] = rc;
+        rc = rc->next;
+        n++;
     }
 
-    return i;
-}
+    // Update pointer
+    for (int i = 0 ; i < length-1 ; i++) {
+        sorted[i]->next = sorted[i+1];
+    }
+    sorted[length-1]->next = NULL;
 
-void ucx_list_qsort_sort(UcxList** list, int l, int r, cmp_func f, void* d) {
-    if (l < r) {
-        int m = ucx_list_qsort_devide(list, l, r, f, d);
-        ucx_list_qsort_sort(list, l, m-1, f, d);
-        ucx_list_qsort_sort(list, m+1, r, f, d);
-    }
+    return sorted[0];
 }
 
 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
     if (l == NULL) {
         return NULL;
     }
-    size_t n = ucx_list_size(l);
-    if (n == 1) {
+
+    UcxList *lc;
+    int ln = 1;
+
+    UcxList *ls = l, *le;
+    lc = ls;
+    while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
+        lc = lc->next;
+        ln++;
+    }
+    le = lc->next;
+
+    UcxList *rs = le, *re;
+    if (rs == NULL) {
+        return l; // this list is already sorted :)
+    } else {
+        UcxList *rc;
+        int rn = 1;
+        rc = rs;
+        while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
+            rc = rc->next;
+            rn++;
+        }
+        re = rc->next;
+
+        // Something left? Sort it!
+        UcxList *remainder = re;
+        size_t remainder_length = ucx_list_size(remainder);
+        if (remainder != NULL) {
+            remainder = ucx_list_sort(remainder, fnc, data);
+        }
+
+        // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
+        UcxList *sorted = ucx_list_sort_merge(ln+rn,
+                ls, rs, le, re,
+                fnc, data);
+
+        // merge sorted list with (also sorted) remainder
+        l = ucx_list_sort_merge(ln+rn+remainder_length,
+                sorted, remainder, NULL, NULL,
+                fnc, data);
+
         return l;
     }
-
-    UcxList *entries[n];
-    entries[0] = l;
-    for (int i = 1 ; i < n ; i++) {
-      entries[i] = entries[i-1]->next;
-    }
-
-    ucx_list_qsort_sort(entries, 0, n-1, fnc, data);
-
-    for (int i = 0 ; i < n-1 ; i++) {
-      entries[i]->next = entries[i+1];
-    }
-    entries[n-1]->next = NULL;
-
-    return entries[0];
 }
 
 /* list specific functions */