別解中では ( Timsort がそうであるように ) 指数探索を用いてマージを実装しましたが、最悪計算量を保証したいだけなら二分探索を用いて実装しても構いません。

実装例 (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;
}