Любую одну задачу на с++

1) две программы (или одна из них) с объяснением принципа работы

ИЛИ

2) консультация (по тому как можно решить, без составления самой программы)

Требования к задачам следующие:

1) сложность меньше квадратичной

2) принцип "разделяй и властвуй" + рекурсивные алгоритмы приветствуются

3) никаких допмассивов, библиотек и std-встроенных функций (типа сортировки, лямбда-выражений и тд)

задачи следующие:

1) умножить матрицу Адамара (2^n*2^n) на вектор столбец без генерации самой матрицы Адамара. Преподаватель сказал, что там какая-то закономерность. Но к сожалению, я ее никак не могу понять.

2) выполнить устойчивое разбиение элементов массива на четную и нечетную часть с сохранением порядка

пример: 3 0 7 5 1 8 4 2 

0 8 4 2 3 7 5 1

тут как-то нужно методом разделяй и властвуй + рекурсивной обработкой.

без допмассива.