diff options
Diffstat (limited to 'ss2016/algodat/01/MergeSort.java')
-rw-r--r-- | ss2016/algodat/01/MergeSort.java | 48 |
1 files changed, 48 insertions, 0 deletions
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 @@ | |||
1 | import java.util.*; | ||
2 | |||
3 | class MergeSort { | ||
4 | public static void mergeSort(int[] a, int from, int to) { | ||
5 | if (from >= to) | ||
6 | return; | ||
7 | |||
8 | int mid = (from + to) / 2; | ||
9 | mergeSort(a, from, mid); | ||
10 | mergeSort(a, mid + 1, to); | ||
11 | merge(a, from, mid, to); | ||
12 | } | ||
13 | |||
14 | public static void merge(int[] a, int from, int mid, int to) { | ||
15 | int[] b = new int[to - from + 1]; | ||
16 | |||
17 | int i, j; | ||
18 | i = from; | ||
19 | j = mid + 1; | ||
20 | |||
21 | for (int k = 0; k < b.length; k++) { | ||
22 | if (j > to || (i <= mid && a[i] < a[j])) { | ||
23 | b[k] = a[i]; | ||
24 | i++; | ||
25 | } else { | ||
26 | b[k] = a[j]; | ||
27 | j++; | ||
28 | } | ||
29 | } | ||
30 | |||
31 | for (int k = 0; k < b.length; k++) { | ||
32 | a[k + from] = b[k]; | ||
33 | } | ||
34 | } | ||
35 | |||
36 | public static void mergeSort(int[] a) { | ||
37 | mergeSort(a, 0, a.length - 1); | ||
38 | } | ||
39 | |||
40 | public static void main (String[] argv) { | ||
41 | int[] a = new int[argv.length]; | ||
42 | for (int i = 0; i < argv.length; i++) | ||
43 | a[i] = Integer.parseInt(argv[i]); | ||
44 | |||
45 | mergeSort(a); | ||
46 | System.out.println(Arrays.toString(a)); | ||
47 | } | ||
48 | } | ||