hybrid sorting algorithm

3 files changed, 37 insertions, 3 deletions

diff --git a/GNUmakefile b/GNUmakefile
index 8283c98..f6651dd 100644
--- a/GNUmakefile
+++ b/GNUmakefile
@@ -1,8 +1,8 @@
 CC=clang --std=gnu99
 
-CFLAGS=-Wall -Wextra -Werror# -g -pg
+CFLAGS=-Wall -Wextra -Werror -g# -pg
 LIBS=
-BLDFLAGS=-O2# -g -pg
+BLDFLAGS=-O2 -g# -pg
 
 TARGET=otc
 DEPS=main.c agenda_entry.c date.c
diff --git a/agenda_entry.c b/agenda_entry.c
index d3fc466..f21ac2a 100644
--- a/agenda_entry.c
+++ b/agenda_entry.c
@@ -69,7 +69,24 @@ char *format_entry(entry e) {
 }
 
 void sort_entry_array(entry *arr, int n) {
-    merge_sort_entry_array(arr, n);
+    if (n == 1) return;
+
+    merge_sort_entry_array(arr,n);
+    return;
+
+    int halfway = n/2;
+    if (n <= 32) {
+        insertion_sort_entry_array(arr, n);
+    } else {
+        if (halfway <= 32) {
+            insertion_sort_entry_array(arr, halfway);
+            insertion_sort_entry_array(arr+halfway, n - halfway);
+        } else {
+            sort_entry_array(arr, halfway);
+            sort_entry_array(arr+halfway, n - halfway);
+        }
+        merge_entry_array(arr, halfway, n);
+    }
 }
 
 void merge_sort_entry_array(entry *arr, int n) {
@@ -82,6 +99,22 @@ void merge_sort_entry_array(entry *arr, int n) {
     merge_entry_array(arr, halfway, n);
 }
 
+void insertion_sort_entry_array(entry *arr, int n) {
+    if (n == 1) return;
+
+    int j = 0;
+    entry sw;
+    for (int i = 1; i < n; i++) {
+        j = i - 1;
+        while (j >= 0 && smaller(arr[j+1].date, arr[j].date)) {
+            sw = arr[j];
+            arr[j] = arr[j+1];
+            arr[j+1] = sw;
+            j--;
+        }
+    }
+}
+
 void merge_entry_array(entry *arr, int halfway, int n) {
     int i = 0,
         j = halfway;
diff --git a/agenda_entry.h b/agenda_entry.h
index fbaef0b..8f13b2d 100644
--- a/agenda_entry.h
+++ b/agenda_entry.h
@@ -22,6 +22,7 @@ entry read_agenda_entry(char *agenda);
 char *format_entry(entry e);
 
 void merge_entry_array(entry *arr, int halfway, int n);
+void insertion_sort_entry_array(entry *arr, int n);
 void merge_sort_entry_array(entry *arr, int n);
 void sort_entry_array(entry *arr, int n);
 void print_entry(entry e);