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