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

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

Да, потому что тебе нужно сдвинуть в среднем половину элементов на одну позицию для каждой вставки.