Медиана медиан, понимающих код

Question

Я нашел реализацию алгоритма в C++ здесь https://gist.github.com/andlima/1774060 но я не понимаю цели нескольких строк и как они работают,

1. Должен ли я добавить оператор if, что если n меньше определенного количества, мы должны просто отсортировать массив и вернуть v[k]?
2. В 4-й строке, почему мы создаем переменную, увеличивая ее на 4? Я понимаю, что мы должны разделить это на 5, чтобы иметь количество маленьких массивов
3. За что отвечает этот цикл for в 6 строке? Это для разделения основного массива на более мелкие, которые мы хотим отсортировать, а затем создать массив медиан? Почему существует функция подкачки и почему мы разделяем ее на условия if и else?
4. Почему мы удаляем массив medians после вызова той же строки функции перед
5. Какова цель цикла в 25 строк и это в 33, а также своп в 38?

Я буду очень благодарен за любую помощь с этим.

Answer 1

1. Это оптимизация. Реализация может сделать это, но это не обязательно.
2. Добавление четырех делается для округления результата деления на пять. Это обычная уловка с целочисленным делением: если вы хотите округлить результат деления на N, добавлять N-1 до разделения.
3. Цикл в строке 6 отвечает за итерацию пятиэлементных фрагментов массива. if условие проверяет, имеет ли кусок пять элементов. for циклы внутри выполняют сортировку выбора, меняя местами элементы, чтобы поместить медиану в индекс w[2]
4. Мы удаляем medians как только закончится рекурсивный вызов, потому что остальной части алгоритма это не нужно.
5. Петля на линии 25 ходов pivot в конечную позицию массива.