From a61b998270e8f955c603de96775e072a555f735d Mon Sep 17 00:00:00 2001
From: Gregor Kleen <gkleen@yggdrasil.li>
Date: Tue, 19 Apr 2016 15:21:02 +0200
Subject: AlgoDat 01

---
 ss2016/algodat/01/MergeSort.java | 48 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 48 insertions(+)
 create mode 100644 ss2016/algodat/01/MergeSort.java

(limited to 'ss2016/algodat/01/MergeSort.java')

diff --git a/ss2016/algodat/01/MergeSort.java b/ss2016/algodat/01/MergeSort.java
new file mode 100644
index 0000000..97f7cfa
--- /dev/null
+++ b/ss2016/algodat/01/MergeSort.java
@@ -0,0 +1,48 @@
+import java.util.*;
+
+class MergeSort {
+    public static void mergeSort(int[] a, int from, int to) {
+        if (from >= to)
+            return;
+        
+        int mid = (from + to) / 2;
+        mergeSort(a, from, mid);
+        mergeSort(a, mid + 1, to);
+        merge(a, from, mid, to);
+    }
+
+    public static void merge(int[] a, int from, int mid, int to) {
+        int[] b = new int[to - from + 1];
+
+        int i, j;
+        i = from;
+        j = mid + 1;
+        
+        for (int k = 0; k < b.length; k++) {
+            if (j > to || (i <= mid && a[i] < a[j])) {
+                b[k] = a[i];
+                i++;
+            } else {
+                b[k] = a[j];
+                j++;
+            }
+        }
+
+        for (int k = 0; k < b.length; k++) {
+            a[k + from] = b[k];
+        }
+    }
+    
+    public static void mergeSort(int[] a) {
+        mergeSort(a, 0, a.length - 1);
+    }
+    
+    public static void main (String[] argv) {
+        int[] a = new int[argv.length];
+        for (int i = 0; i < argv.length; i++)
+            a[i] = Integer.parseInt(argv[i]);
+        
+        mergeSort(a);
+        System.out.println(Arrays.toString(a));
+    }
+}
-- 
cgit v1.2.3