Add merge sort tests

3 files changed, 99 insertions, 0 deletions

diff --git a/src/03/sort.c b/src/03/sort.c
index e69de29..9be5253 100644
--- a/src/03/sort.c
+++ b/src/03/sort.c
@@ -0,0 +1,32 @@
+#include <stdio.h>
+
+void _merge(int *items, int min, int pivot, int max)
+{
+  if (items[min] > items[pivot]) {
+    int tmp[max-min];
+    for (int i = pivot; i < max; i++)
+      tmp[i] = items[i];
+    for (int i = min; i < pivot; i++)
+      tmp[max + i] = items[i];
+    for (int i = 0; i < max-min; i++)
+      items[min+i] = tmp[i];
+  }
+}
+
+void _merge_sort(int *items, int min, int max)
+{
+  if (!items || max == min)
+    return;
+
+  int pivot = ((max - min) / 2) + min;
+  _merge_sort(items, min, pivot);
+  _merge_sort(items, pivot + 1, max);
+  _merge(items, min, pivot + 1, max);
+}
+
+void merge_sort(int *items, int length) {
+  if (!items || length <= 0)
+    return;
+
+  _merge_sort(items, 0, length - 1);
+}
diff --git a/src/03/sort.h b/src/03/sort.h
index e69de29..4226490 100644
--- a/src/03/sort.h
+++ b/src/03/sort.h
@@ -0,0 +1 @@
+void merge_sort(int *items, int length);
diff --git a/src/03/sort_test.c b/src/03/sort_test.c
index 3dae1d1..6ee5d63 100644
--- a/src/03/sort_test.c
+++ b/src/03/sort_test.c
@@ -6,8 +6,74 @@ Ensure(one_equals_one) {
   assert_that(1, is_equal_to(1));
 }
 
+Ensure(merge_sort_sorts_a_null_list) {
+  merge_sort(NULL, 0);
+}
+
+Ensure(merge_sort_sorts_an_empty_list) {
+  int items[] = {};
+
+  merge_sort(items, 0);
+
+  assert_that(sizeof(items), is_equal_to(0));
+}
+
+Ensure(merge_sort_sorts_a_list_with_one_item) {
+  int items[] = {100};
+
+  merge_sort(items, 1);
+
+  assert_that(sizeof(items), is_equal_to(sizeof(int)));
+  assert_that(items[0], is_equal_to(100));
+}
+
+Ensure(merge_sort_sorts_a_list_with_two_items) {
+  int items[] = {100, 10};
+
+  merge_sort(items, 2);
+
+  assert_that(sizeof(items), is_equal_to(sizeof(int) * 2));
+  assert_that(items[0], is_equal_to(10));
+  assert_that(items[1], is_equal_to(100));
+}
+
+Ensure(merge_sort_sorts_three_unique_items) {
+  int items[] = { 3, 1, 4 };
+
+  merge_sort(items, sizeof(items) / sizeof(int));
+
+  assert_that(items[0], is_equal_to(1));
+  assert_that(items[1], is_equal_to(3));
+  assert_that(items[2], is_equal_to(4));
+}
+
+Ensure(merge_sort_sorts_many_items) {
+  int items[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
+
+  merge_sort(items, sizeof(items) / sizeof(int));
+
+  assert_that(items[0], is_equal_to(1));
+  assert_that(items[1], is_equal_to(1));
+  assert_that(items[2], is_equal_to(2));
+  assert_that(items[3], is_equal_to(3));
+  assert_that(items[4], is_equal_to(3));
+  assert_that(items[5], is_equal_to(4));
+  assert_that(items[6], is_equal_to(5));
+  assert_that(items[7], is_equal_to(5));
+  assert_that(items[8], is_equal_to(5));
+  assert_that(items[9], is_equal_to(6));
+  assert_that(items[10], is_equal_to(9));
+}
+
 TestSuite *sort_tests() {
   TestSuite *x = create_test_suite();
   add_test(x, one_equals_one);
+
+  add_test(x, merge_sort_sorts_a_null_list);
+  add_test(x, merge_sort_sorts_an_empty_list);
+  add_test(x, merge_sort_sorts_a_list_with_one_item);
+  add_test(x, merge_sort_sorts_a_list_with_two_items);
+  add_test(x, merge_sort_sorts_three_unique_items);
+  add_test(x, merge_sort_sorts_many_items);
   return x;
 }