1 files changed, 38 insertions, 0 deletions
diff --git a/sortnet.c b/sortnet.c
new file mode 100644
index 0000000..fd99a17
--- /dev/null
+++ b/sortnet.c
@@ -0,0 +1,38 @@
+#include <stddef.h>
+#include <stdint.h>
+
+#include "common.h"
+
+static const uint8_t sortnet[][2] = {
+	/* 0: index =  0 */
+	/* 1: index =  0 */
+	/* 2: index =  0 */
+	{0,1},
+	/* 3: index =  1 */
+	{0,1}, {0,2}, {1,2},
+	/* 4: index =  4 */
+	{0,1}, {2,3}, {0,2}, {1,3}, {1,2},
+	/* 5: index =  9 */
+	{0,1}, {3,4}, {2,4}, {2,3}, {1,4}, {0,3}, {0,2}, {1,3}, {1,2},
+	/* 6: index = 18 */
+	{1,2}, {4,5}, {0,2}, {3,5}, {0,1}, {3,4}, {2,5}, {0,3}, {1,4}, {2,4},
+	{1,3}, {2,3},
+	/* 7: index = 30 */
+	{1,2}, {3,4}, {5,6}, {0,2}, {3,5}, {4,6}, {0,1}, {4,5}, {2,6}, {0,4},
+	{1,5}, {0,3}, {2,5}, {1,3}, {2,4}, {2,3},
+	/* 8: index = 46 */
+	{0,1}, {2,3}, {4,5}, {6,7}, {0,2}, {1,3}, {4,6}, {5,7}, {1,2}, {5,6},
+	{0,4}, {3,7}, {1,5}, {2,6}, {1,4}, {3,6}, {2,4}, {3,5}, {3,4},
+	/* 9: index = 65, if we used a sorting network this large */
+};
+
+static const uint8_t sortnet_index[] = { 0, 0, 0, 1, 4, 9, 18, 30, 46, 65 };
+
+void sorting_network(char *base, size_t nmel, size_t width, cmpfun cmp)
+{
+	for (int i = sortnet_index[nmel]; i < sortnet_index[nmel+1]; i++) {
+		char *elem1 = base + sortnet[i][0] * width;
+		char *elem2 = base + sortnet[i][1] * width;
+		if (cmp(elem1, elem2) > 0) swap(elem1, elem2, width);
+	}
+}