sort и двумерный массив

3 10 5 3 6
1 3  7 8 3

3 3 5 6 10

1 8 7 3 3

3 3 5 6 10
1 8 7 3 3

Ну, лично бы я просто бы создал vector <pair <int, int>> vect и сделал бы сортировку sort(vect.begin(), vect.end()).
Ну, а выводить так - первый цикл выведет первые элементы пар, сделает перевод строки и второй цикл выведет вторые элементы пар.

Если есть возможность оперировать столбцами вашей матрицы, как единым элементом, то задача решена - сортируем столбцы и готово.

Если такой возможности нет, то простейшим решением будет свести решение к предыдущему: скопировать матрицу в другую матрицу, где столбцы хранятся компактно, отсортировать ее и скопировать результат обратно.

Если такие варианты не устраивают, т.е. требуется отсортировать матрицу "на месте", без создания копии, то сделать это можно разными более хитрыми способами.

1. Можно создать линейный итератор, который работает сразу со столбцом матрицы, несмотря на то, что столбец хранится некомпактно. Такой итератор можно написать самому. Похожий итератор есть в готовом виде в Boost под именем zip_iterator, но он является итератором "только для чтения".

   Готового решения я не нашел, а реализация его с нуля получается довольно громоздкой

   #include <tuple>
   #include <vector>
   #include <algorithm>
   #include <iostream>
   template <typename ...R> struct swap_tuple : std::tuple<R...>
   {
     using std::tuple<R...>::tuple;
     using std::tuple<R...>::operator =;
     friend void swap(const swap_tuple &lhs, const swap_tuple &rhs)
     {
       using namespace std;
       swap(std::get<0>(lhs), std::get<0>(rhs));
       swap(std::get<1>(lhs), std::get<1>(rhs));
       // ...
     }
   };
   template <typename IT>
   class It2
   {
   public:
     using iterator_category = std::random_access_iterator_tag;
     using difference_type = std::ptrdiff_t;
     using pointer = void;
     using value_type = swap_tuple<typename IT::value_type, typename IT::value_type>;
     using reference = swap_tuple<typename IT::reference, typename IT::reference>;
     It2(IT it1, IT it2) : its(it1, it2) {}
     reference operator *() const
       { return reference{ *std::get<0>(its), *std::get<1>(its) }; }
     It2 &operator ++() 
       { ++std::get<0>(its); ++std::get<1>(its); return *this; }
     It2 operator ++(int) 
       { It2 old = *this; ++*this; return old; }
     It2 &operator +=(std::ptrdiff_t rhs) 
       { std::get<0>(its) += rhs; std::get<1>(its) += rhs; return *this; }
     friend It2 operator +(const It2 &lhs, std::ptrdiff_t rhs)
       { return It2(lhs) += rhs; }
     It2 &operator --() 
       { --std::get<0>(its); --std::get<1>(its); return *this; }
     It2 operator --(int) 
       { It2 old = *this; --*this; return old; }
     It2 &operator -=(std::ptrdiff_t rhs) 
       { std::get<0>(its) -= rhs; std::get<1>(its) -= rhs; return *this; }
     friend It2 operator -(const It2 &lhs, std::ptrdiff_t rhs)
       { return It2(lhs) -= rhs; }
     friend std::ptrdiff_t operator -(const It2 &lhs, const It2 &rhs)
       { return std::get<0>(lhs.its) - std::get<0>(rhs.its); }
     friend bool operator ==(const It2 &lhs, const It2 &rhs)
       { return lhs.its == rhs.its; }
     friend bool operator !=(const It2 &lhs, const It2 &rhs)
       { return !(lhs == rhs); }
     friend bool operator <(const It2 &lhs, const It2 &rhs)
       { return lhs.its < rhs.its; }
   private:
     std::tuple<IT, IT> its;
   };
   int main() 
   {
     std::vector<std::vector<int>> m = 
       { { 3, 10, 5, 3, 6 }, { 1, 3, 7, 8, 3 } };
     It2<std::vector<int>::iterator> 
       it_begin(m[0].begin(), m[1].begin()), 
       it_end(m[0].end(), m[1].end());
     std::sort(it_begin, it_end);
     // Результат
     for(const auto &r : m)
     {
       for(auto v : r)
         std::cout << v << " ";
       std::cout << std::endl;
     }
   }
   

2. Использовать "сортирующую перестановку". Выполнить сортировку индексного массива {0, 1, 2, 3, 4, ...} с соответствии с первой строкой матрицы. Получить в результате перестановку, которая будет описывать новый порядок элементов. В вашем примере это будет {0, 3, 2, 4, 1}. Затем применить эту перестановку "на месте" ко всем строкам матрицы.

   Например (заимствуя функцию применения перестановки отсюда, ибо в стандартной библиотеке, как ни странно, готовой нет)

   #include <vector>
   #include <numeric>
   #include <algorithm>
   #include <iostream>
   void apply_permutation(std::vector<int>& v,
                          std::vector<unsigned> indices)
   {
     for (unsigned i = 0; i < indices.size(); i++) 
     {
       unsigned current = i;
       while (i != indices[current]) 
       {
         unsigned next = indices[current];
         std::swap(v[current], v[next]);
         indices[current] = current;
         current = next;
       }
       indices[current] = current;
     }
   }
   int main() 
   {
     std::vector<std::vector<int>> m = 
       { { 3, 10, 5, 3, 6 }, { 1, 3, 7, 8, 3 } };
     // Строим сортирующую перестановку
     std::vector<unsigned> index(m[0].size());
     std::iota(index.begin(), index.end(), 0);
     std::sort(index.begin(), index.end(), 
       [&](unsigned i, unsigned j) { return m[0][i] < m[0][j]; });
     // Переупорядочиваем строки
     apply_permutation(m[0], index);
     apply_permutation(m[1], index);
     // Результат
     for(const auto &r : m)
     {
       for(auto v : r)
         std::cout << v << " ";
       std::cout << std::endl;
     }
   }
   

Ещё одно решение - это модифицировать какой нибудь обменный алгоритм сортировки, который бы меняя местами элементы в первой строке, сделал бы "аналогичные" обмены для элементов остальных строк.

Для примера возьмём сортировку выбором, и модифицируем её.

#include <iostream>
#include <vector>
void special_sort(std::vector<std::vector<int>>& v)
{
    size_t rows = v.size();
    size_t cols = v[0].size();
    for (size_t i = 0; i < cols; ++i)
    {
        size_t maxi = 0;
        for (size_t j = 0; j < cols - i; ++j)
        {
            if (v[0][j] > v[0][maxi])
            {
                maxi = j;
            }
        }
        // индекс маскимального элемента в первой строке найден
        // обмениваем его с последним
        std::swap(v[0][maxi], v[0][cols - i - 1]);

        // Стоит заметить, что после обмена, последний элемент на следующей итерации
        // больше не будет нужен, поэтому можно считать что он уже на своем месте
        // далее обмениваем по этим же индексам элементы остальных строк
        for (size_t k = 1; k < rows; ++k)
        {
            std::swap(v[k][maxi], v[k][cols - i - 1]);
        }
    }
}
int main()
{
    std::vector<std::vector<int>> v = { {3, 10, 5, 3, 6},
                                        {1, 3,  7, 8, 3}
                                    };
    special_sort(v);
    for (const auto& i : v)
    {
        for (const auto& j : i)
        {
            std::cout << j << ' ';
        }
        std::cout << '\n';
    }
    return 0;
}