writing sorting code is what drones are for

1 files changed, 81 insertions, 12 deletions

diff --git a/src/seq.c b/src/seq.c
index e0854f5..1edfe24 100644
--- a/src/seq.c
+++ b/src/seq.c
@@ -64,26 +64,95 @@ error_malloc_item:
     return -1;
 }
 
-static void event_sort(xas_seq *seq) {
-    xas_seq_event_list_item *item = seq->first,
-                              *temp = NULL;
+static xas_seq_event_list_item *event_list_tail(xas_seq_event_list_item *head) {
+    if (head == NULL) {
+        return NULL;
+    }
 
-    while (item) {
-        temp = item;
+    while (head->next) {
+        head = head->next;
+    }
+
+    return head;
+}
+
+static xas_seq_event_list_item *event_list_partition(xas_seq_event_list_item *head,
+                                                       xas_seq_event_list_item *end,
+                                                       xas_seq_event_list_item **head_new,
+                                                       xas_seq_event_list_item **end_new) {
+    xas_seq_event_list_item *pivot = end,
+                              *prev  = NULL,
+                              *cur   = head,
+                              *tail  = pivot;
+
+    while (cur != pivot) {
+        if (timercmp(&cur->ev->timestamp, &pivot->ev->timestamp, <)) {
+            if (*head_new == NULL) {
+                *head_new = cur;
+            }
 
-        while (temp->next) {
-            if (timercmp(&temp->ev->timestamp, &temp->next->ev->timestamp, >)) {
-                xas_seq_event *ev = temp->ev;
+            prev = cur;
+            cur  = cur->next;
+        } else {
+            xas_seq_event_list_item *tmp;
 
-                temp->ev       = temp->next->ev;
-                temp->next->ev = ev;
+            if (prev) {
+                prev->next = cur->next;
             }
 
-            temp = temp->next;
+            tmp = cur->next;
+
+            cur->next  = NULL;
+            tail->next = cur;
+            tail       = cur;
+            cur        = tmp;
         }
+    }
 
-        item = item->next;
+    if (*head_new == NULL) {
+        *head_new = pivot;
     }
+
+    *end_new = tail;
+
+    return pivot;
+}
+
+static xas_seq_event_list_item *event_list_sort_recur(xas_seq_event_list_item *head,
+                                                        xas_seq_event_list_item *end) {
+    xas_seq_event_list_item *head_new = NULL,
+                              *end_new  = NULL,
+                              *pivot;
+
+    if (head == NULL || head == end) {
+        return head;
+    }
+
+    pivot = event_list_partition(head, end, &head_new, &end_new);
+
+    if (head_new != pivot) {
+        xas_seq_event_list_item *tmp = head_new;
+
+        while (tmp->next != pivot) {
+            tmp = tmp->next;
+        }
+
+        tmp->next = NULL;
+
+        head_new = event_list_sort_recur(head_new, tmp);
+
+        tmp = event_list_tail(head_new);
+        tmp->next = pivot;
+    }
+
+    pivot->next = event_list_sort_recur(pivot->next, end_new);
+
+    return head_new;
+}
+
+static void event_sort(xas_seq *seq) {
+    seq->first = event_list_sort_recur(seq->first, seq->last);
+    seq->last  = event_list_tail(seq->first);
 }
 
 int xas_seq_add_event_off(xas_seq *seq,