Differences

This shows you the differences between two versions of the page.

--- algorithms [2009/03/06 20:01] – created moritz
+++ algorithms [2009/03/10 17:30] (current) – Add mergesort moritz
@@ Line 54: / Line 54: @@
                 return;
         }
+    }
+}
+</code>
+==== Mergesort ====
+This implementation is rather ugly, however, it seems to work.
+<code java>
+package ch.ethz.da.serie3;
+/**
+ * Sample implementation of 2 way natural merge sort..
+ *
+ * @author Moritz Hoffmann
+ *
+ */
+public class Mergesort {
+    private int sLength = 0;
+    private int[] source;
+    private int sStart = -1;
+    private int[] target;
+    /**
+     * Construct new sorter instance.
+     *
+     * @param v
+     *            The values to sort. Call {@link Mergesort#sort()} to start
+     *            sorting.
+     */
+    public Mergesort(int[] v) {
+        source = v;
+        target = new int[source.length];
+    }
+    public int[] getValues() {
+        return source;
+    }
+    /**
+     * Sort the array the object was created with.
+     */
+    public void sort() {
+        resetRun();
+        boolean swap = true;
+        while (sStart + sLength + 1 < source.length) {
+            nextRun();
+            if (sStart > source.length || sLength == source.length - 1) {
+                swap = false;
+                break;
+            }
+            int s = sStart;
+            int l = sLength;
+            nextRun();
+            if (sStart < source.length) {
+                System.out.println("Merging " + s + ":" + l + " with " + sStart
+                        + ":" + sLength);
+                merge(s, l);
+                // System.out.println(Arrays.toString(target));
+            } else {
+                System.arraycopy(source, s, target, s, l + 1);
+                resetRun();
+                int[] t = target;
+                target = source;
+                source = t;
+            }
+        }
+        if (swap) {
+            int[] t = target;
+            target = source;
+            source = t;
+        }
+    }
+    /**
+     * Merge the sequence sStart + sLength with the sequence described by the
+     * arguments/
+     *
+     * @param s
+     *            The sequence's start.
+     * @param l
+     *            The sequence's length.
+     */
+    private void merge(int s, int l) {
+        // pointer to current target
+        int pv = s;
+        // pointer to the position in the first run
+        int pa = s;
+        // pointer to the position in the second run.
+        int pb = sStart;
+        // end of new run.
+        int ev = s + l + sLength + 2;
+        // end of first run.
+        int ea = s + l + 1;
+        // end of second run
+        int eb = sStart + sLength + 1;
+        // merge part
+        while (pa < ea && pb < eb) {
+            int da = source[pa];
+            int db = source[pb];
+            if (da <= db) {
+                target[pv] = da;
+                pa = pa + 1;
+            } else {
+                target[pv] = db;
+                pb = pb + 1;
+            }
+            pv = pv + 1;
+        }
+        // copy part
+        if (pv < ev) {
+            if (pa < ea) {
+                // first part is longer.
+                System.arraycopy(source, pa, target, pv, ea - pa);
+            } else {
+                // second part must be longer.
+                System.arraycopy(source, pb, target, pv, eb - pb);
+            }
+        }
+    }
+    /**
+     * Get the length of the next sorted sequence. Result is stored in sStart
+     * and sLength.
+     */
+    private void nextRun() {
+        int i = sStart + sLength + 1;
+        sStart = i;
+        final int length = source.length - 1;
+        while (i < length && source[i] <= source[i + 1]) {
+            i++;
+        }
+        sLength = i - sStart;
+    }
+    /**
+     * Reset sStart and sLength to their initial values after reaching the end
+     * of the array.
+     */
+    private void resetRun() {
+        sLength = 0;
+        sStart = -1;
     }
 }
 </code>