#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <cmath>

using namespace std;

string commaify(int N)
{ string s;
  int count = 0;
  while (N > 0)
  { if (count == 3)
    { s += ',';
      count = 0; }
    s += (char)(N % 10 + '0');
    count += 1;
    N /= 10; }
  for (int i = 0, j = s.length() - 1; i < j; i += 1, j -= 1)
    swap(s[i], s[j]);
  return s; }

const double minute = 60.0;
const double hour = 60.0 * minute;
const double day = 24.0 * hour;
const double week = 7.0 * day;
const double month = 30.5 * day;
const double year = 365.25 * day;
const double century = 100.0 * year;
const double gigayear = 1.0e9 * year;

string time(double numops)
{ const double time_one_op = 1.0e-9;   // 1 nano-second, a bit optimistic
  const double time = numops * time_one_op;
  ostringstream os;
  if (time < 1.0e-6)
    os << fixed << setprecision(2) << time / 1.0e-9 << " nano-seconds";
  else if (time < 1.0e-3)
    os << fixed << setprecision(2) << time / 1.0e-6 << " micro-seconds";
  else if (time < 1.0)
    os << fixed << setprecision(2) << time / 1.0e-3 << " milliseconds";
  else if (time < minute)
    os << setprecision(2) << time << " seconds";
  else if (time < hour)
    os << setprecision(2) << time / minute << " minutes";
  else if (time < day)
    os << setprecision(2) << time / hour << " hours";
  else if (time < week)
    os << setprecision(2) << time / day << " days";
  else if (time < year)
    os << setprecision(2) << time / month << " months";
  else if (time < century)
    os << setprecision(2) << time / year << " years";
  else if (time < gigayear)
    os << commaify((int)(time / year)) << " years";
  else
    os << scientific << setprecision(2) << time / year << " years";
  return os.str(); }

int main()
{ cout << scientific << "\n";
  cout << "                       merge sort                          selection sort\n";
  cout << "    N        operations           time             operations           time               ratio\n";
  cout << " -------     ----------   --------------------     ----------   --------------------      --------\n";
  for (double N = 1000.0; N < 2e12; N *= 10.0)
  { const double msops = 5.0 * N * log2(N),
                 ssops = 0.5 * N * N;
    cout << " " << setprecision(1) << setw(6) << N << 
            setprecision(5) << 
            "      " << setprecision(3) << msops << "  " << setw(21) << time(msops) <<
            "      " << setprecision(3) << ssops << "  " << setw(21) << time(ssops) <<
            "      " << setprecision(2) << ssops / msops << "\n"; }
  cout << "\n"; }