Есть упорядоченный массив неких структур. Условие упорядочивания весьма сложное, и функция сравнения достаточно дорогая. При помощи этого массива выполняется некая обработка в две фазы. Каждая фаза состоит из N циклов. В каждом цикле из массива сначала удаляется несколько элементов (возможно что и все), потом добавляется несколько других из кучи (куча большая). При добавлении, элементы вставляются в нужное место в массиве в соотвествии с условиями упорядоченности (бинарный поиск, потом — вставка). Затем выполняется вторая фаза обработки. При этом важно, чтобы на каждом цикле второй фазы элементы в массиве в точности соответствовали элементам того же цикла на первой фазе. Но исходного условия упорядочивания у нас уже нет. Казалось бы все просто, надо завести в структуре поле в которое на первой фазе записывать позицию для вставки. Но проблема в том, что порядок выборки элементов из кучи на второй фазе может быть немного другим. При этом гарантируется, что на каждом цикле будут те же самые элементы, но внутри одного цикла они поступают в другом порядке. Таким образом, надо изобрести некий искусственный индекс, определяющий порядок сортировки на первой фазе (в качестве некого поля в куче). Я испробовал следующий простейший способ. В качестве индекса берем число типа double. На первой фазе: Если массив пустой, присваиваем индексу значение 0. Далее, если вставка происходит в конец, присваиваем последний+1. Если в начало, то первый-1. Если куда-то в середину, то (a+b)/2. Где a и b — элементы, между которыми выполняется вставка. Это все работает, но только до определенного предела. При наихудшем раскладе после 53 элементов происходит сбой по понятной причине — a и b становятся одинаковыми. А надо уметь вставлять тысячи элементов. Все это очень напоминает бинарное дерево, требующее периодической балансировки. Но по ряду причин дерево как таковое использовать нельзя, да и не поможет оно. Что бы такое еще хитрое придумать?

Насколько я понял, использование индексов в твоем случае не оправдано, т.к. ты фактически записываешь в индексе номер возможной втсавки. Именно по этому индекс насышается к 53-ему шагу -- рост количества варинатов экспоненциальный.

Ты не мог бы описать алгоритм в псевдокоде, со слов понять трудновато?

Можно конечно придумать адаптивную схему индексации, но тогда нужно будет O(N*N) время на ее поддержку, что для 1000 элементов нереально.

Вопрос конечно глупый, но почему бы не поделить вставку на два этапа, на первом вставляем элементы, на втором -- нумеруем? Другими словами, после каждого цикла переиндексировать элементы из массива?