diff options
1 files changed, 26 insertions, 0 deletions
| -rw-r--r-- | Year 1/Object-oriented Programming/10-Practice-03.05.2022/MergeSort.hpp | 26 |
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); +} |