#include <iostream>
#include <string>
#include <fstream>
using namespace std;


struct Node
{
    string info;
    Node * next;
    Node (const string& s, Node * after)
	: info(s), next(after)
    {
	    
    }
};

bool inOrder(Node * list)
{
    Node * trail = list;
    list = list->next;
    while (list != 0){
	if (trail->info > list->info){
	    return false;
	}
	trail = list;
	list = list->next;
    }
    return true;
}

Node * merge(Node * a, Node * b)
{
    if (a == 0) return b;
    if (b == 0) return a;

    if (a->info <= b->info){
	a->next = merge(a->next,b);
	return a;
    }
    else {
	b->next = merge(a,b->next);
	return b;
    }
}

int size(Node * list)
{
    int count = 0;
    while (list != 0){
	count++;
	list = list->next;
    }
    return count;
}

static int counter = 0;

Node * sort(Node * list)
{
    if (list != 0 && list->next != 0){
	counter++;
	if (counter % 100 == 0) cout << counter << " " << size(list) << endl;
	Node * first = list;
	Node * second = 0;

	Node * trail = list;
	list = list->next->next;
	
	while (list != 0){
	    trail = trail->next;
	    list = list->next;
	    if (list != 0){
		list = list->next;
	    }
	}
	second = trail->next;
	trail->next = 0;

	first = sort(first);
	second = sort(second);
	return merge(first,second);
    }
    return list;
}

Node * sort2(Node * list)
{
    if (list != 0 && list->next != 0){

	Node * first = list;
	Node * second = list->next;
	
	list = list->next->next;
	first->next = 0;
	second->next = 0;
	
	while (list != 0){
	    Node * unseen = list->next;
	    list->next = first;
	    first = list;
	    list = unseen;
	    if (list != 0){
		unseen = list->next;
		list->next = second;
		second = list;
		list = unseen;
	    }
	}
	first = sort2(first);
	second = sort2(second);

	return merge(first,second);
    }
    return list;
}



int main(int argc, char * argv[])
{
    string filename;
    if (argc > 1){
	filename = argv[1];
    }
    else {
	cout << "filename: ";
	cin >> filename;
    }
    string word;
    Node * list = 0;

    ifstream input(filename.c_str());

    while (input >> word){
	list = new Node(word,list);
    }
    cout << "size of list = " << size(list) << endl;
    list = sort2(list);
    if (! inOrder(list)){
	cout << "trouble" << endl;
    }
    cout << "size of list = " << size(list) << endl;    
}