From 169cbc9a9a36ef2d0c71d35bc2086a061982df95 Mon Sep 17 00:00:00 2001
From: Syndamia <kamen.d.mladenov@protonmail.com>
Date: Tue, 3 May 2022 21:04:38 +0300
Subject: Finished todays practice

---
 .../10-Practice-03.05.2022/MergeSort.hpp           | 26 ++++++++++++++++++++++
 1 file changed, 26 insertions(+)
 create mode 100644 Year 1/Object-oriented Programming/10-Practice-03.05.2022/MergeSort.hpp

(limited to 'Year 1/Object-oriented Programming/10-Practice-03.05.2022/MergeSort.hpp')

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);
+}
-- 
cgit v1.3.1-26-gb76a