Здравствуйте, Pzz, Вы писали:

Pzz>А вот если кранить его не списком, а сбалансированным деревом, то построение списка со вставкой элементов на нужное место будет стоить O(n * Ln(n)).

Хе-хе, я все-таки угадал со вставкой О(n*logn), но я ошибался в том, что вставка в отсортированый массив будет О(logn), а она на самом деле О(n). Почему О(n) я пока не понял, из-за копирования что ли?