#include <iostream>
#include <string>

using namespace std;

string merge(string str1, string str2) {
  string final = "";
  int i = 0, j = 0;
  bool fromStr1 = false;

  while (true) {
    if (i >= (int)str1.size()) {
      break;
    }
    if (j >= (int)str2.size()) {
      fromStr1 = true; // changed the order of this with break!
      break;
    }

    if (str1[i] < str2[j]) {
      final += str1[i];
      i++;
    }
    else {
      final += str2[j];
      j++;
    }
  }

  if (fromStr1) {
    for (int t = i; t < (int)str1.size(); t++) {
      final += str1[t];
    }
  }
  else {
    for(int t = j; t < (int)str2.size(); t++) {
      final += str2[t];
    }
  }

  return final;
}

string mergeSort(string str1) {
  int len = str1.size();
  if (len <= 1)
    return str1;
  else {
    string newStr1 = mergeSort(str1.substr(0, len / 2));
    string newStr2 = mergeSort(str1.substr(len / 2, len - len / 2));
    return merge(newStr1, newStr2);
  }
}

int main()
{
  cout << '"' << mergeSort("") << '"' << endl;
  cout << '"' << mergeSort("a") << '"' << endl;
  cout << '"' << mergeSort("ba") << '"' << endl;
  cout << '"' << mergeSort("132") << '"' << endl;
  cout << '"' << mergeSort("4321") << '"' << endl;
  cout << '"' << mergeSort("54321") << '"' << endl;
  return 0;
}