In the alternative solution, we implemented merging using an exponential search, but if you just want to guarantee the worst time complexity, you may just run binary search.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

template <class RandomAccessIterator, class Compare> constexpr void binary_merge_sort(
  RandomAccessIterator first, RandomAccessIterator last, Compare comp){
  auto len=(last-first);
  if(len<=1){return;}

  auto mid=first+len/2;
  binary_merge_sort(first,mid,comp);
  binary_merge_sort(mid,last,comp);

  auto a=vector(first,mid);
  auto b=vector(mid,last);
  auto ai=a.begin();
  auto bi=b.begin();
  bool side=false;
  while(ai!=a.end() || bi!=b.end()){
    if(ai==a.end()){
      while(bi!=b.end()){
        (*first)=(*bi);
        first++; bi++;
      }
      break;
    }
    else if(bi==b.end()){
      while(ai!=a.end()){
        (*first)=(*ai);
        first++; ai++;
      }
      break;
    }
    side=(!side);
    if(side){
      // kick a.begin();
      long long c=0;
      long long d=(1ll<<(63-__builtin_clzll(b.end()-bi)));
      while(d>=1){
        auto it=ranges::next(bi,c+d-1,b.end());
        if(it==b.end()){d>>=1;continue;}
        if(comp((*it),(*ai))){c+=d;}
        d>>=1;
      }
      while(c--){
        (*first)=(*bi);
        first++; bi++;
      }
      (*first)=(*ai);
      first++; ai++;
    }
    else{
      // kick b.begin();
      long long c=0;
      long long d=(1ll<<(63-__builtin_clzll(a.end()-ai)));
      while(d>=1){
        auto it=ranges::next(ai,c+d-1,a.end());
        if(it==a.end()){d>>=1;continue;}
        if(comp((*it),(*bi))){c+=d;}
        d>>=1;
      }
      while(c--){
        (*first)=(*ai);
        first++; ai++;
      }
      (*first)=(*bi);
      first++; bi++;
    }
  }
}

bool comp(const string &x,const string &y){
  return (x+y < y+x);
}

string concat(vector<string> &s){
  string res="";
  for(auto &nx : s){ res+=nx; }
  return res;
}

int main(){
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    vector<string> s(n);
    for(auto &nx : s){cin >> nx;}
    binary_merge_sort(s.begin(),s.end(),comp);

    if(n==2){
      cout << s[1]+s[0] << "\n";
      continue;
    }
    
    bool ok=false;
    for(int i=1;i<n;i++){
      if(s[i-1]+s[i] == s[i]+s[i-1]){ok=true; break;}
    }
    if(ok){
      cout << concat(s) << "\n";
      continue;
    }

    swap(s[n-1],s[n-2]);
    string c1=concat(s);
    swap(s[n-1],s[n-2]);
    swap(s[n-2],s[n-3]);
    cout << min(c1,concat(s)) << "\n";
  }
  return 0;
}