Sort vector of vector [duplicate]

This question already has an answer here:

• Sort vector of vectors 3 answers

I have a vector of vectors of int like this:

std::vector<std::vector<int>> vec_vec{{3,5,1,6},{2,4},...};

The results should be

 Case1:   {{1, 2, 3, 4}, {5, 6}} 
 Case2:  {1,2,3,4,5,6}
 Case3:  {{1, 3, 5, 6}, {2, 4}} 

I found many ways to do this, the best one I found need complexity O(n^2) to sort them.

What's the best complexity for the case1, case2 and case3?

So what's the best way to write a native (c++11,c++14) cross platform code to sort that's vector? is O(n^2) is the best complexity? The memory is important also.

I checked this solution here, but it seems it also took O(n^2) to sort the vectors?