#include <iostream>
#include <string>
#include <sstream>

using namespace std;

class List
{ protected:

    struct Link
    { string data;
      Link * next;

      Link(string d, Link * n = NULL)
      { data = d;
        next = n; } };

    Link * first;
    Link * last;

  public:
    List()
    { first = NULL;
      last = NULL; }

    ~List()
    { while (first != NULL)
      { Link * next = first->next;
        delete first;
        first = next; } }

    bool is_present(string wanted)
    { Link * ptr = first;
      while (ptr != NULL)
      { if (ptr->data == wanted)
          return true;
        ptr = ptr->next; }
      return false; }

    void add_to_end(string it)
    { if (first == NULL)
      { first = new Link(it, first);
        last = first;
        return; }
      last->next = new Link(it, NULL);
      last = last->next; }

    void add_to_front(string it)
    { if (first == NULL)
      { first = new Link(it, first);
        last = first;
        return; }
      first = new Link(it, first); }

    void print()
    { Link * ptr = first;
      while (ptr != NULL)
      { cout << ptr->data << " ";
        ptr = ptr->next; }
      cout << "\n"; }

    bool remove(string unwanted)
    { Link * ptr = first, * prev = NULL;
      while (ptr != NULL)
      { if (ptr->data == unwanted)
        { if (prev == NULL)
            first = ptr->next;
          else
            prev->next = ptr->next;
          delete ptr;
          return true; }
        prev = ptr;
        ptr = ptr->next; }
      return false; }

    bool is_empty()
    { return first == NULL; }

    string remove_first()
    { if (first == NULL)
        return NULL;
      string value = first->data;
      Link * next = first->next;
      delete first;
      first = next;
      return value; }

    void delete_all()
    { while (first != NULL)
      { Link * next = first->next;
        delete first;
        first = next; } }

    void read()
    { delete_all();
      string line;
      getline(cin, line);
      istringstream iss(line);
      while (true)
      { string s;
        iss >> s;
        if (iss.fail())
          break;
        add_to_end(s); } }

    void append(List & X)
    { if (X.first == NULL)
        return;
      if (first == NULL)
      { first = X.first;
        last = X.last; }
      else
      { last->next = X.first;
        last = X.last; }
      X.first = NULL;
      X.last = NULL; }

    void split(List & A, List & B)
    { A.delete_all();
      B.delete_all();
      while (true)
      { if (is_empty())
          break;
        string i = remove_first();
        A.add_to_end(i);
        if (is_empty())
          break;
        string j = remove_first();
        B.add_to_end(j); } }

    void merge(List & A, List & B)
    { delete_all();
      while (! A.is_empty() && ! B.is_empty())
      { string s;
        if (A.first->data < B.first->data)
          s = A.remove_first();
        else
          s = B.remove_first();
        add_to_end(s); }
      if (! A.is_empty())
        append(A);
      else
        append(B); }

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

    void sort()
    { if (is_very_short())
        return;
      List M, N;
      split(M, N);
      M.sort();
      N.sort();
      merge(M, N); } };

List reverse(List & L)
{ List result;
  while (! L.is_empty())
  { string i = L.remove_first();
    result.add_to_front(i); }
  return result; }

int main()
{ List L;

  cout << "original list: ";
  L.read();

  L.sort();

  cout << "sorted list: ";
  L.print(); }