path: root / Year 1 / Object-oriented Programming / 10-Practice-03.05.2022 / MergeSort.hpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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);
}