# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1725200074 -7200
# Node ID 608b14deea182c4340efed75e7c8e8608437fb6c
# Parent  f4ce7df9cff04c73a5c5765fd5bbe45c1ba55810
optimize default insert_sorted implementation

resolves #418

diff -r f4ce7df9cff0 -r 608b14deea18 src/list.c
--- a/src/list.c	Sun Sep 01 14:48:43 2024 +0200
+++ b/src/list.c	Sun Sep 01 16:14:34 2024 +0200
@@ -308,14 +308,62 @@
         void const *sorted_data,
         size_t n
 ) {
+    // corner case
+    if (n == 0) return 0;
+
     size_t elem_size = list->collection.elem_size;
     cx_compare_func cmp = list->collection.cmpfunc;
     char const *src = sorted_data;
 
-    size_t r = cx_list_default_insert_array(list, 0, src, n);
-    cx_list_default_sort(list);
+    // track indices and number of inserted items
+    size_t di = 0, si = 0, inserted = 0;
+
+    // search the list for insertion points
+    for (; di < list->collection.size; di++) {
+        void const *list_elm = invoke_list_func(at, list, di);
+
+        // compare current list element with first source element
+        // if less or equal, skip
+        if (cmp(list_elm, src) <= 0) {
+            continue;
+        }
 
-    return r;
+        // determine number of consecutive elements that can be inserted
+        size_t ins = 1;
+        char const *next = src;
+        while (++si < n) {
+            next += elem_size;
+            // once we become larger than the list elem, break
+            if (cmp(list_elm, next) <= 0) {
+                break;
+            }
+            // otherwise, we can insert one more
+            ins++;
+        }
+
+        // insert the elements at location si
+        if (ins == 1) {
+            if (0 != invoke_list_func(insert_element,
+                                      list, di, src))
+                return inserted;
+        } else {
+            size_t r = invoke_list_func(insert_array, list, di, src, ins);
+            if (r < ins) return inserted + r;
+        }
+        inserted += ins;
+        di += ins;
+
+        // everything inserted?
+        if (inserted == n) return inserted;
+        src = next;
+    }
+
+    // insert remaining items
+    if (si < n) {
+        inserted += invoke_list_func(insert_array, list, di, src, n - si);
+    }
+
+    return inserted;
 }
 
 void cx_list_default_sort(struct cx_list_s *list) {