Finished todays practice

1 files changed, 26 insertions, 0 deletions

diff --git a/Year 1/Object-oriented Programming/10-Practice-03.05.2022/MergeSort.hpp b/Year 1/Object-oriented Programming/10-Practice-03.05.2022/MergeSort.hpp
new file mode 100644
index 0000000..68129b6
--- /dev/null
+++ b/Year 1/Object-oriented Programming/10-Practice-03.05.2022/MergeSort.hpp
@@ -0,0 +1,26 @@
+#include <iostream>
+
+template <typename T>
+T* merge(T* left, T* right, unsigned lsize, unsigned rsize) {
+	unsigned size = lsize + rsize;
+	T* merged = new T[size];
+	for (int i = 0; i < size; i++) {
+		if (rsize == 0 || (lsize != 0 && *left < *right)) { 
+			merged[i] = *(left++);
+			lsize--;
+		}
+		else { 
+			merged[i] = *(right++);
+			rsize--;
+		}
+	}
+	return merged;
+}
+
+template <typename T>
+T* mergeSort(T* arr, unsigned size) {
+	if (size == 1) return arr;
+
+	unsigned leftSize = size / 2, rightSize = size - leftSize;
+	return merge(mergeSort(arr, leftSize), mergeSort(arr + leftSize, rightSize), leftSize, rightSize);
+}