Реализации алгоритмов/Сортировка/Слиянием: различия между версиями

* @brief Сортировка элементов от lleft до rright массива buf

* @param[in] lleft - левая граница. При первой итерации lleft = 0

* @param[in] rright - правая граница. При первой итерации rright = buf.size() - 1

* В результате сортируются все элементы массива buf от lleft до rright включительно.

void MergeSort(vector<Type>& buf, size_t lleft, size_t rright)

if(lleft >= rright) return;

size_t mmiddle = (lleft + r(right - left) / 2;

MergeSort(buf, lleft, mmiddle);

MergeSort(buf, mmiddle + 1, rright);

merge(buf, lleft, rright, mmiddle);

* @param[in] lleft - левая граница. При певой итерации lleft = 0

* @param[in] rright - правая граница. При первой итерации rright = buf.size() - 1

* @param[in] mmiddle - граница подмассивов.

* - [lleft; mmiddle] - первый отсортированный подмассив.

* - [mmiddle+1; rright] - второй отсортированный подмассив.

* который сохраняется в buf[lleft; rright].

static void merge(vector<Type>& buf, size_t lleft, size_t rright, size_t mmiddle)

if (lleft >= rright || mmiddle < lleft || mmiddle > rright) return;

if (rright == lleft + 1 && buf[lleft] > buf[rright]) {

swap(buf[lleft], buf[rright]);

vector<Type> tmp(&buf[lleft], &buf[lleft] + (rright + 1));

for (size_t i = lleft, j = 0, k = mmiddle - lleft + 1; i <= rright; ++i) {

if (j > mmiddle - lleft) {

} else if(k > rright - lleft) {

* l1len_1 - Длина первого массива

* l2len_2 - Длина второго массива

T* merge(T *m1, T* m2, int l1len_1, int l2len_2)

T* ret = new T[l1len_1+l2len_2];

while (l1len_1 && l2len_2) {

--l1len_1;

--l2len_2;

if (l1len_1 == 0) {

for (int i = 0; i < l2len_2; ++i) {

for (int i = 0; i < l1len_1; ++i) {

int n = 1, lk, ost;

lk = 0;

while (lk < len) {

if (lk + n >= len) break;

ost = (lk + n * 2 > len) ? (len - (lk + n)) : n;

mas1 = merge(mas + lk, mas + lk + n, n, ost);

mas[lk+i] = mas1[i];//тут нужно что-то поменять, потому что это лишнее копирование, и оно увеличивает время работы алгоритма в два раза

lk += n * 2;

void MergeSort(Item a[], int lleft, int rright)

int mmiddle;

if(lleft >= rright) return;

mmiddle = (lleft + r(right - left) / 2;

MergeSort(a, lleft, mmiddle);

MergeSort(a, mmiddle + 1, rright);

Merge(a, lleft, rright, mmiddle);