Нет ли способа вставить в отсортированный массив новый элемент за O(log n)?[size=3]

Бинарный поиск попробуй. По крайней мере найти место для вставки за O(log n) операций ты точно сможешь... Как у тебя массив реализован? В смысле, это именно массив или список?

Структура - обыкновенный массив (но при желании можно изменить).
Вся проблема в том и состоит, что мало найти место, необходимо двигать хвост. А как это сделать меньше чем за О(n)?
Может быть применить другую структуру данных?

Если будешь использовать связанный список (linked list), то нет никакой необходимости сдвигать хвост, элемент за одно действие вставится в любое место списка...

А как организовать бинарный поиск в связном списке?

Стоп... Ты задачу конкретно сформулируй... Что тебе нужно добиться? Чтобы любая операция в какой-либо структуре данных выполнялась за O(log n), или именно в массиве сохранять упорядоченность за O(log n) операций?

Какие еще операции будут выполняться над данными? Использование RB-деревьев возможно?

Более конкретная формулировка:
необходимо организовать такую структуру натуральных чисел, из которой на каждом шаге берутся
два минимальных элемента и складываются, после чего их сумма возвращается в структуру, и так
до тех пор пока в стуктуре останется один элемент.
Вся программа должна работать за О(n*log n).
В структуре могут быть повторяющиеся элементы.

А ты Красно-Чёрные деревья пробовал, ну или АВЛ-деревья?
Думаю должно прокатить, вот только я не помню время вставки-удаления.

А вот ещё вариант: у нас есть уже отсортированный массив чисел. При сумме двух минимальных мы пытаемся найти вхождение этого числа в массив - если не находим, то добавляем в список, ассоциированный с ближайшим меньшим/большим числом (соответственно список тоже должен быть отсортированным). В противном случае (если вхождение нашли) то инкрементим счётчик вхождений данного числа.
По моему это будет эффективно и должны уложиться в О(н*Лог(н)).

Что я и предлагал:
Насколько я помню, при хорошей реализации в RB-дереве гарантируется оценка O(logn) для операций.