Можете помочь с алгоритмом сортировки?

Question

[Yermek]

Начал читать тут основы алгоритмов Тима Рафгардена, и в ведении дается аргоритм сортировки слиянием. Я его реализовал так.

Но мне очень не нравится блок условий в merge. Но без него сортировка не идёт :,(

Подсобите плиз советом, как правильно объединять.

Comments

[Евгений Самсонов]

Что конкретно не нравится?

[Евгений Самсонов]

Так лучше?
https://play.golang.org/p/HTgHIxseXSq

[Yermek]

Евгений Самсонов, само наличие доп двух условий

[Yermek]

Евгений Самсонов,

Так лучше?

Да, эстетичнее. Спасибо.

Получается, что без этих проверок никак? М/б есть какой финт ушами?

[Евгений Самсонов]

Yermek, Не вдавался в детали, надо вспоминать алгоритм

[Yermek]

Евгений Самсонов, нашел. Двигаться надо по результирующему массиву, а индексы сливаемых инкрементировать в зависимости от того, откуда взяли очередное значение:

https://play.golang.org/p/wTDYeoJKITs

Answer 1

[Mercury13]

1. Вам свезло, что длина массива — ровно 8, то есть степень двойки. Ваш алгоритм никак не приспособлен к тому, что на очередном шаге длина массива окажется нечётной.
2. Я не знаю, как происходит слайсинг массивов и передача параметров в Go, но надо проверять, насколько много перевыделения лишней памяти.
3. Опять свезло — левая и правая половинки расходуются очень равномерно: один слева — один справа. Если взять отсортированный массив { 1, 2, 3, 4, 5, 6, 7, 8 }, когда сначала расходуем левую половинку, потом правую — должно заглючить. На самом деле слияние массивов содержит ещё больше всяких условий, и на каждом сравнении мы кладём в результирующий массив не два элемента из разных массивов, а один — меньший. И соответственно сдвигаем один из индексов-кареток.

Comments

[Yermek]

Спасибо. Помогло. Все везение это результат допущений, что бы избежать лишних условый, о которых Вы говорите.
Касательно памяти - там передаются срезы - как я понял, указатели на начало отрезка в исходном массиве и длина среза. Лишней памяти съедаться не должно, а временные кешы создаются сразу нужной длинны, и по выходу съедаются сборщиком мусора.

Ваше третье замечание тоже отразил в результирующем коде https://play.golang.org/p/wTDYeoJKITs

[Wataru]

Yermek, Используйте цикл while. Не умею в го, но что-то типа такого там можно записать:

while (i1 < len(a1) && i2 < len(a2)) {
  if (a1[i1] < a2[i2]) {
    r[k++] = a1[i1];
  } else {
    r[k++] = a2[i2];
  }
}
while (i1 < len(a1)) r[k++] = a1[i1];
while (i1 < len(a2)) r[k++] = a2[i2];

Первый цикл выбирает меньгий эелемнт, пока есть оба массива. Далее остатки одного из двух массивов просто копируюутся в ответ.

[Yermek]

wataru, похоже, что будет так