template <class T> T FindMin(T *t, int iCnt)
{
  T tMin = t[0];

  while (--iCnt > 0)
  {
    if (t[iCnt] < tMin)
        tMin = t[iCnt];
  }

  return tMin;
}

template <class T> void Sort(T **t, int iCntX, int iCntY)
{
  for (int iY2 = 0; iY2 < iCntY; ++iY2)
  {
    for (int iY = 1; iY < iCntY; ++iY)
    {
      if (FindMin(t[iY - 1], iCntX) > FindMin(t[iY], iCntX)
      {
        // Переставляем местами строки
      }
    }
  }
}

int main()
{
   vector<vector<int> > arr2d(3);
   arr2d[0].push_back(2);
   arr2d[0].push_back(3);
   arr2d[0].push_back(5);

   arr2d[1].push_back(5);
   arr2d[1].push_back(6);
   arr2d[1].push_back(7);

   arr2d[2].push_back(1);
   arr2d[2].push_back(2);
   arr2d[2].push_back(2);

   //Вектор пар: первое значение - минимальный элемент строки, второе значение - номер строки
   vector<pair<int, size_t> > rows(arr2d.size());

   for(size_t i = 0; i < arr2d.size(); ++i)
   {
      pair<int, size_t> p(*min_element(arr2d[i].begin(), arr2d[i].end()), i);
      rows[i] = p;
   }

   //стандартный оператор сравнения для pair<> вполне подходит
   sort(rows.begin(), rows.end());

   //трансформируем исходный массив в сортированный без копирования элементов
   vector<vector<int> > arr2d_sorted(3);
   for(size_t j = 0; j < rows.size(); ++j)
      arr2d_sorted[j].swap(arr2d[rows[j].second]);
   
   //Возвращаем все в исходный массив, опять же без копирования
   arr2d.swap(arr2d_sorted);
   return 0;
}

N - количество строк
sizeof(pair<int, size_t>)*N + N*sizeof(vector<>)

А>Мне кажется, что подобных задач использование STL несколько избыточно.

А>P.S. Может мне просто не нравится STL.

int minEl(int *vectOfM)
{
  int  minEl =  vectOfM[0];
  for(int j=1;j<m;j++)
    if(minEl>vectOfM[j]) minEl = vectOfM[j];
  return minEl;
}

void SortMatr(int **Matrca,int n,int m) 
{
int *vect;
vect = new int[n];
for(int i = 0; i<n; i++)
   vect[i]=minEl(Matrca[i]);
for(int i = n-1; i>=0; i--)
 for(int j = 0; j<i; i++)
   if(vect[i]<vect[j])
      {
        перествили vect[i] vect[j]
        переставили Matrc[i] Matrc[j]
      }
delete vect;
}

__>int minEl(int *vectOfM)
__>{
__>  int  minEl =  vectOfM[0];
__>  for(int j=1;j<m;j++)
__>    if(minEl>vectOfM[j]) minEl = vectOfM[j];
__>  return minEl;
__>}

__>void SortMatr(int **Matrca,int n,int m) 
__>{
__>int *vect;
__>vect = new int[n];
__>for(int i = 0; i<n; i++)
__>   vect[i]=minEl(Matrca[i]);
__>for(int i = n-1; i>=0; i--)
__> for(int j = 0; j<i; i++)
__>   if(vect[i]<vect[j])
__>      {
__>        перествили vect[i] vect[j]
__>        переставили Matrc[i] Matrc[j]
__>      }
__>delete vect;
__>}
__>

delete vect;

#include <vector>
#include <algorithm>
#include <functional>
#include <boost/bind.hpp>
using namespace std;

template <class T, class U> U unwrap(T t) { return *t; }

int main()
{
    vector<vector<int> > v(3);
    typedef vector<int>::iterator IteratorType;
    for_each(v.begin(), v.end(), boost::bind(&vector<int>::resize, _1, 3));
    v[0][0] = 6; v[0][1] = 4; v[0][2] = 8;
    v[1][0] = 7; v[1][1] = 9; v[1][2] = 3;
    v[2][0] = 2; v[2][1] = 1; v[2][2] = 5;

    // вся работа в одной строчке
    sort(v.begin(), v.end(), boost::bind<bool>(less<size_t>(), boost::bind<size_t>(&unwrap<IteratorType, size_t>, boost::bind<IteratorType>(&min_element<IteratorType>, boost::bind(&vector<int>::begin, _1), boost::bind(&vector<int>::end, _1))), boost::bind<size_t>(&unwrap<IteratorType, size_t>, boost::bind<IteratorType>(&min_element<IteratorType>, boost::bind(&vector<int>::begin, _2), boost::bind(&vector<int>::end, _2)))));
    
    return 0;
}