屁理屈を言うと、index_listを壊していいなら、
以下の手順で別領域を使わない置換は可能。遅いけど。
for( size_t i = 0; i < array.size() - 1; ++i )
{
std::swap( array[i], array[index_list[i]] );
std::swap( index_list[i], *std::find( index_list.begin()+i+1, index_list.end(), i ) );
}