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

_>В результате регулярное добавление занимает ~15% времени выполнения, сортировка ~60%.
_>Какие можно предпринять шаги чтобы ускорить все это хозяйство?

А почему бы Вам не использовать std::map<int, int> для того что бы всегда иметь отсортированные данные?

Для добавления каждого нового элемента потребуется О(Log(N)), где N — количество элементов внутри мэпа.
За то они всегда будут отсортированы, и всё что нужно для того что бы создать отсортированый список уникалов это — пробежаться от begin() до end() по мэпу, с проверкой двух соседних элементов на неравенство, за O(N).

скажем так...

    map<int, int> sorted_map;

    for (int i = 0; i < 10000; i++) {
        //генерируем новый элемент
        int new_val = rand(); 
        //добавляем в мэп
        sorted_map.insert(pair<int,int>(new_val, new_val)); 
        //если нужно выделить уникалов? определяется случайно...
        if (i && rand() % 100 == 0) { 
            map<int, int>::iterator it = sorted_map.begin(); 
            int prev_val = it->second; //сохраняем предидущий
            printf("%d ");
            //бежим по мэпу
            for (it++; it != sorted_map.end(); it++) { 
                //проверяем с предидущим 
                if (it->second != prev_val) { 
                    printf("%d ", it->second); //принтим уникальный элемент        
                    prev_val = it->second; //сохраняем предидущий
                }
            }
            printf("\r\n");
        }
    }