#include <fstream>
using namespace std;

// Defines the structure for a node in the doubly-linked list.
class node {
public:
  int value;
  node *next, *prev;
  node::node() {
    next = NULL;
    prev = NULL;
  }
  node::~node() {
    delete next;
    delete prev;
  }
};

// Regular sort.
void InsertionSort(node *head, node *tail) {
  int key;
  node *left, *right = head->next;
  while (right) {
    key = right->value;
    left = right;
    while (left->prev && left->prev->value > key){
      left->value = left->prev->value;
      left = left->prev;
    }
    left->value = key;
    right = right->next;
  }
}

// Basic sort which will swap two integers if the first one is greater.
void OrderPair(int &x, int &y) {
  if (x > y) {
    int scratch = x;
    x = y;
    y = scratch;
  }
}

// Swap unordered pairs in a spiral fashion.
void SpiralPatch(node *head, node *tail) {
  node *left = head, *right = tail;
  while (left != right && left->prev != right) {
    OrderPair(left->value, right->value);
    left = left->next;
    OrderPair(left->value, right->value);
    right = right->prev;
  }
}

// This wrapper applies the spiral patch and then runs a regular sort.
void SpiralSort(node *head, node *tail) {
  SpiralPatch(head, tail);
  InsertionSort(head, tail);
}

// Main program loads input, sorts, and saves output.
int main(int argc, char* argv[]) {
  int scratch;
  node *first = NULL, *last = NULL, *temp;

  // Ensure command-line arguments.
  // Does not check if input file exists!
  if (argc != 3) return -1;

  // Load input file into list.
  ifstream infile(argv[1]);
  while (!infile.eof()) {
    infile >> scratch;
    if (infile.good()) {
      if (first) {
	last->next = new node;
	last->next->prev = last;
	last->next->value = scratch;
	last = last->next;
      }
      else {
	first = new node;
	first->value = scratch;
	last = first;
      }
    }
  }
  infile.close();

  // Apply sorting algorithm.
  SpiralSort(first, last);

  //Save output file from list.
  ofstream outfile(argv[2]);
  temp = first;
  while (temp != NULL) {
    outfile << temp->value << endl;
    temp = temp->next;
  }
  outfile.close();

  return 0;
}