[maxkar]

Тормоза кода связаны с тем, что ваш компаратор генерирует полную фигню на выходе. От него вообще-то ожидается, что если a < b, то b > a. А у вас если a == null и b == null указанное не выполняется. Поэтому можно даже и корректности сортировки не получить.

1. В первую очередь из-за того, что его размер не меняется, экономятся перераспределения памяти. Вполне может быть, что просто отсутствие изменения размера массива (с fixed == false) по быстродействию окажется таким же, что и при fixed == true.

2. А почему вы решили, что обращение идет итератором или по списку? Вектор то (в отличие от массива) плотная (dense) структура, на ней эффективно реализуется индексный доступ. В том числе и для resizeable vector, с амортизированной сложностью добавления и удаления в конец списка O(1).