1 files changed, 53 insertions, 0 deletions
diff --git a/week2/Mergesort.cs b/week2/Mergesort.cs
new file mode 100644
index 0000000..b9810b5
--- /dev/null
+++ b/week2/Mergesort.cs
@@ -0,0 +1,53 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace ALGA {
+	public class Mergesort {
+		public static void mergesort(ISortList list) {
+			if (list.Count <= 1) return;
+			mergesort(list, 0, list.Count - 1);
+		}
+
+		public static void mergesort(ISortList list, int leftIndex, int rightIndex) {
+			if (leftIndex > rightIndex) return;
+			if (rightIndex - leftIndex <= 0) return;
+
+			int middle = (leftIndex + rightIndex) / 2;
+			mergesort(list, leftIndex, middle);
+			mergesort(list, middle + 1, rightIndex);
+			merge(list, leftIndex, middle, rightIndex);
+		}
+
+		private static void merge(ISortList list, int leftIndex, int middleIndex, int rightIndex) {
+			int leftSize = middleIndex - leftIndex + 1;
+			ISortList left = new SortList(leftSize);
+			for (int i = 0; i < leftSize; i++) left[i] = list[leftIndex + i];
+
+			int rightSize = rightIndex - middleIndex;
+			ISortList right = new SortList(rightSize);
+			for (int i = 0; i < rightSize; i++) right[i] = list[middleIndex + 1 + i];
+
+			int leftOffset = 0;
+			int rightOffset = 0;
+			for (int i = leftIndex; i <= rightIndex; i++) {
+				if (leftOffset == leftSize) {
+					list[i] = right[rightOffset++];
+					continue;
+				}
+				if (rightOffset == rightSize) {
+					list[i] = left[leftOffset++];
+					continue;
+				}
+
+				if (left[leftOffset] < right[rightOffset])
+					list[i] = left[leftOffset++];
+				else
+					list[i] = right[rightOffset++];
+			}
+		}
+	}
+}
+