Код представлен на С++, рекурсивная функция сортировки слиянием, _с - это количество сравнений, m -количество перемещений, intVec - vector
void CSort::simpleMerge(intVec& _sortingVec, int64_t& _c, int64_t& m, int begin = 0,int end = -1) {
if (end == -1) {
end = _sortingVec.size();
}
if (end - begin< 2) {
return;
}
else if (end - begin == 2) {
_c++;
if (_sortingVec.at(begin) > _sortingVec.at(begin+1)) {
m++;
int b = _sortingVec.at(begin);
_sortingVec.at(begin) = _sortingVec.at(begin + 1);
_sortingVec.at(begin + 1) = b;
}
return;
}
simpleMerge(_sortingVec,_c,m, begin, begin + (end - begin) / 2);
simpleMerge(_sortingVec, _c, m, begin + (end - begin) / 2,end);
intVec c;
size_t begin1 = begin;
size_t begin2 = begin + (end - begin) / 2;
size_t end1 = begin2;
while (c.size() < end-begin)
{
_c++;
if ((begin1>=end1) or(begin2<end and _sortingVec.at(begin2) <= _sortingVec.at(begin1))) {
c.push_back(_sortingVec.at(begin2));
m++;
begin2++;
}
else {
c.push_back(_sortingVec.at(begin1));
m++;
begin1++;
}
}
for (size_t i = begin; i < end; i++)
{
_sortingVec.at(i) = c.at(i-begin);
}
}