Здравствуйте, вот такой вопрос. Можно реализовать следующий алгоритм за время меньшее чем O(n*log(n)):

В массиве целые числа, они неупорядочены. Из него выбираются два наименьших числа, они удаляются из массива. Затем в него добаляется сумма этих двух чисел. Добавляем эту сумму в переменную s. Далее запускаем этот же алгоритм для нового массива. Когда осталось одно число — пишем на экран значение s.

Выбор наименьшего можно сделать за O(log(n)) операций, кроме того эта функция запускается n-1 раз, n — длина массива. Всего O(log(n))*(n-1)=O(n*log(n)). Логика вроде верная, но скорости не хватает. Может я что то не так понял? Помогите мне разобраться.

Вот моя функция выбора минимума(метод дерева), если найдёте ошибку(вдруг она есть) — буду очень благодарен:

long min(long* m, long l, long r)
{
 long p;
 long i;
 long a1, a2;
 if(l == r) return l;
 else {
  p = int((l+r)/2);
  a1 = min(m, l, p);
  a2 = min(m, p+1, r);
 }
 if(m[a1]<m[a2]) return a1;
 else return a2;
}