Сортировка двух соответствующих массивов

Вам нужно объединить их вместе, а затем отсортировать объединенную пару и затем не объединять пары.

int arr[ 5 ] = { ... };
string arr1[ 5 ] = { ... };
pair<int, string> pairs[ 5 ];

for ( int i = 0; i < 5; ++i )
  pairs[ i ] = make_pair( arr[ i ], arr1[ i ] );

sort( pairs.begin(), pairs.end() );

for ( int i = 0; i < 5; ++i )
{
  arr[ i ] = pairs[ i ].first;
  arr1[ i ] = pairs[ i ].second;
}

Действительно, хотя, если arr и arr1 связаны, они должны быть сохранены как pair (или, по крайней мере, пользовательские struct) в любом случае. Таким образом, вам не нужно использовать это в качестве промежуточного шага.

Я считаю, что написание собственного варианта QuickSort проще, и результат будет лучше, чем отображение пользовательских итераторов или массива с индексами.

Быстрая сортировка не является стабильной сортировкой.

template<class A, class B> void QuickSort2Desc(A a[], B b[], int l, int r)
{               
    int i = l;
    int j = r;
    A v = a[(l + r) / 2];
    do {
        while (a[i] > v)i++;
        while (v > a[j])j--;
        if (i <= j)
        {
            std::swap(a[i], a[j]);
            std::swap(b[i], b[j]);          
            i++;
            j--;
        };
    } while (i <= j);
    if (l < j)QuickSort2Desc(a, b, l, j);
    if (i < r)QuickSort2Desc(a, b, i, r);
}