add non-recursive MergeSort

ramona.burger · abranhe · commit de7d9280ee41 · 2020-10-06T16:47:57.000-04:00
diff --git a/sorting/MergeSortNonRecursive.java b/sorting/MergeSortNonRecursive.java
@@ -0,0 +1,56 @@
+public class NonRecursiveMergeSort<T extends Comparable<T>> {
+
+	public T[] MergeSort(T[] M) {
+
+		int length = M.length;
+		int size = 1;
+		int p;
+		while (size < length) {
+			p = -1;
+			while (p + size < length) {
+				int left = p + 1;
+				int right = left + size - 1;
+				if (right + size <= length) {
+					p = right + size;
+				} else {
+					p = length;
+				}
+				merge(M, left, right, p);
+			}
+			size = size * 2;
+		}
+
+		return M;
+
+	}
+
+
+	public T[] merge(T[] M, int left, int right, int p) {
+		int i = left;
+		int j = right + 1;
+		int k = left;
+		T[] M2 = M.clone();
+		for (int n = 0; n < M.length; n++) {
+			M2[n] = null;
+		}
+		while (i <= right && j <= p) {
+			if (M[i].compareTo(M[j]) <= 0) {
+				M2[k] = M[i];
+				i = i + 1;
+			} else {
+				M2[k] = M[j];
+				j = j + 1;
+			}
+			k = k + 1;
+		}
+		for (int h = i; h <= right; h++) {
+			M[k + (h - i)] = M[h];
+		}
+		for (int h = left; h <= (k - 1); h++) {
+			M[h] = M2[h];
+		}
+		return M;
+
+	}
+
+}
