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

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

Для однозначного ответа маловато информации, да и все равно нужно экспериментировать.
Могу привести несколько вариантов:
1. std::set вместо вектора
2. inplace_merge вместо std::sort
3. tbb::parallel_sort вместо std::sort
4. своя реализация некоторой структуры данных вместо вектора(какая именно — зависит от характера данных)
5. свяо реализация сортировки, которая может заодно и unique сделать.