#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <cmath>
#include <cassert>
#include <cctype>

using namespace std;

int random_in_range(int min, int max)
{ return random() % (max - min + 1) + min; }

string random_string(int min_length, int max_length)
{ string result;
  result += (char)random_in_range('A', 'Z');
  int len = random_in_range(min_length, max_length);
  for (int i = 1; i <len; i += 1)
    result += (char)random_in_range('a', 'z');
  return result; }

int ops;

class list
{ protected:

    class link
    { public:
        string data;
        link * next;
        link(string d, link * n = NULL)
        { data = d;
          next = n; } };

    link * first, * last;

  public:

    class enumerator
    { protected:
        link * ptr;

      public:
        enumerator(link * x)
        { ptr = x; }

        bool any_more() const
        { return ptr != NULL; }

        string get_next()
        { if (ptr == NULL)
            throw runtime_error("get_next on empty enumerator");
          string result = ptr->data;
          ptr = ptr->next;
          return result; } };

    list()
    { first = NULL;
      last = NULL; }

    void clear()
    { while (first != NULL)
      { link * next = first->next;
        delete first;
        first = next; }
      last = NULL; }

    ~list()
    { clear(); }

    bool empty() const
    { return first == NULL; }

    enumerator get_enumerator() const
    { return enumerator(first); }

    void add_to_front(string s)
    { if (first == NULL)
      { first = new link(s);
        last = first; }
      else
        first = new link(s, first); }

    void add_link_to_front(link * x)
    { x->next = first;
      first = x; }

    void add_to_end(string s)
    { if (first == NULL)
      { first = new link(s);
        last = first; }
      else
      { last->next = new link(s);
        last = last->next; } }

    void add_link_to_end(link * x)
    { ops += 1;
      if (first == NULL)
      { first = x;
        last = x; }
      else
      { x->next = NULL;
        last->next = x;
        last = x; } }

    string see_first() const
    { if (first == NULL)
        throw runtime_error("see_first on empty list");
      return first->data; }

    string remove_first()
    { if (first == NULL)
        throw runtime_error("remove_first on empty list");
      link * old = first;
      first = first->next;
      string result = old->data;
      delete old;
      return result; }

    link * remove_first_link()
    { if (first == NULL)
        throw runtime_error("remove_first_link on empty list");
      ops += 1;
      link * old = first;
      first = first->next;
      old->next = NULL;
      return old; }

    void split(list & x, list & y)
    { x.clear();
      y.clear();
      while (true)
      { if (first == NULL)
          break;
        x.add_link_to_front(remove_first_link());
        if (first == NULL)
          break;
        y.add_link_to_front(remove_first_link()); } }

    void merge(list & x, list & y)
    { clear();
      while (! x.empty() && ! y.empty())
      { ops += 1;
        if (x.see_first() < y.see_first())
          add_link_to_end(x.remove_first_link());
        else
          add_link_to_end(y.remove_first_link()); }
      while (! x.empty())
        add_link_to_end(x.remove_first_link());
      while (! y.empty())
        add_link_to_end(y.remove_first_link()); }

    bool fewer_than_two() const
    { return first == NULL || first->next == NULL; }

    void sort()
    { if (fewer_than_two())
        return;
      list x, y;
      split(x, y);
      x.sort();
      y.sort();
      merge(x, y); } };

int main(int argc, char * argv[])
{ int number = 16;
  if (argc > 1)
    number = atol(argv[1]);
  srandomdev();
  
  list a;
  for (int i = 0; i < number; i += 1)
    a.add_to_end(random_string(5, 7));

  ops = 0;

  a.sort();

  cout << ops << " operations\n"; }