From 403678ce69d3992fbe72bd3cf9030eec67aaaed8 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Fri, 28 Jan 2011 16:11:13 -0500
Subject: Use insertion sort for small lists, new list test.

---
 libdimension/list.c | 34 +++++++++++++++++++++++++---------
 1 file changed, 25 insertions(+), 9 deletions(-)

(limited to 'libdimension/list.c')

diff --git a/libdimension/list.c b/libdimension/list.c
index 421a56e..3eaaa12 100644
--- a/libdimension/list.c
+++ b/libdimension/list.c
@@ -56,8 +56,8 @@ void
 dmnsn_delete_list(dmnsn_list *list)
 {
   if (list) {
-    while (list->first) {
-      dmnsn_list_remove(list, list->first);
+    while (dmnsn_list_first(list)) {
+      dmnsn_list_remove(list, dmnsn_list_first(list));
     }
     dmnsn_free(list);
   }
@@ -97,23 +97,39 @@ dmnsn_list_split(dmnsn_list *list)
 void
 dmnsn_list_sort(dmnsn_list *list, dmnsn_list_comparator_fn *comparator)
 {
-  /* Recursive merge sort */
   if (dmnsn_list_size(list) < 2) {
     return;
-  } else if (dmnsn_list_size(list) == 2) {
-    if ((*comparator)(list->last, list->first)) {
-      dmnsn_list_swap(list->first, list->last);
-    }
+  } else if (dmnsn_list_size(list) <= 16) {
+    /* Use insertion sort on small lists */
+    dmnsn_list_iterator *current = dmnsn_list_next(dmnsn_list_first(list));
+    do {
+      dmnsn_list_iterator *next = dmnsn_list_next(current);
+      dmnsn_list_iterator_remove(list, current);
+
+      dmnsn_list_iterator *i = next;
+      do {
+        dmnsn_list_iterator *prev = i ? dmnsn_list_prev(i)
+                                      : dmnsn_list_last(list);
+        if (!(*comparator)(current, prev))
+          break;
+        i = prev;
+      } while (i != dmnsn_list_first(list));
+      dmnsn_list_iterator_insert(list, i, current);
+
+      current = next;
+    } while (current);
   } else {
+    /* Recursive merge sort */
     dmnsn_list half;
     dmnsn_list_split_impl(list, &half);
     dmnsn_list_sort(list, comparator);
     dmnsn_list_sort(&half, comparator);
 
-    dmnsn_list_iterator *i = list->first, *j = half.first;
+    dmnsn_list_iterator *i = dmnsn_list_first(list);
+    dmnsn_list_iterator *j = dmnsn_list_first(&half);
     while (i || j) {
       if (!i) {
-        j->prev = list->last;
+        j->prev = dmnsn_list_last(list);
         list->last->next = j;
         list->last = half.last;
         list->length += half.length;
-- 
cgit v1.2.3