#include <iostream>
#include <iomanip>
#include <string>
#include <stdlib.h>
#include <math.h>

struct task
{ int * array_to_sort;
  int start_position, end_position;
  task()
  { }
  task(int * a, int b, int c)
  { array_to_sort = a;
    start_position = b;
    end_position = c; } };

struct to_do_list_link
{ task current;
  to_do_list_link * next;
  to_do_list_link(task a, to_do_list_link * b)
  { current = a;
    next = b; } };

struct to_do_list
{ to_do_list_link * first;
  to_do_list()
  { first = NULL; }
  void add(task a)
  { first = new to_do_list_link(a, first); }
  bool not_empty()
  { if (first==NULL)
      return false;
    else
      return true; }
  task take()
  { task result = first->current;
    to_do_list_link * temp = first->next;
    delete first;
    first = temp;
    return result; }
  void printall()
  { cout << "[";
    to_do_list_link * ptr = first;
    while (ptr!=NULL)
    { cout << ptr->current.start_position << "-" << ptr->current.end_position;
      ptr=ptr->next;
      if (ptr!=NULL)
        cout << ", "; }
    cout << "]"; } };

void exchange(int & a, int & b)
{ int temp = a;
  a = b;
  b = temp; }

void prompt(string s)
{ cout << s << "    ";
  getline(cin, s); }

void display(int * A, int s, int e, int p, int q, int pivot)
{ cout << "                                 pivot = " << pivot << "\n";
  for (int i=s; i<=e; i+=1)
  { if (i==s)
      cout << "   start ";
    else if (i==e)
      cout << "     end ";
    else
      cout << "         ";
    if (i==p)
      cout << "P";
    else
      cout << " ";
    if (i==q)
      cout << "Q";
    else
      cout << " ";
    cout << " [" << setw(2) << i << "]: " << setw(5) << A[i] << "\n"; } }

int median(int * A, int pa, int pb, int pc)
{ int a=A[pa], b=A[pb], c=A[pc];
  if (a<=b && b<=c) return pb;
  if (a<=c && c<=b) return pc;
  if (b<=a && a<=c) return pa;
  if (b<=c && c<=a) return pc;
  if (c<=a && a<=b) return pa;
  if (c<=b && b<=a) return pb;
  return pa; }

void sort(int * arr, int size)
{ int number_of_operations = 0;
  to_do_list agenda;
  agenda.add(task(arr, 0, size-1));
  while (agenda.not_empty())
  { cout << "--------------------------------------------------------\n";
    cout << "Agenda: ";
    agenda.printall();
    cout << "\n";
    task to_do = agenda.take();
    int * A = to_do.array_to_sort;
    int start = to_do.start_position;
    int end = to_do.end_position;
    int number = end-start+1;
    if (number<=1)
      continue;
    if (number==2)
    { if (A[start]>A[end])
        exchange(A[start], A[end]);
      continue; }
    int middle = (start+end)/2;
    int pivotpos = median(A, start, middle, end);
    int pivot = A[pivotpos];
    cout << "sorting from position " << start << " to " << end << ", "
         << "candidates for pivot: " << A[start] << " " << A[middle] << " " << A[end] << ", "
         << "pivot=" << pivot << "\n";
    int P=start, Q=end;
    display(A, start, end, P, Q, pivot);
    while (P<Q)
    { cout << "phase a: move P up while A[P] <= pivot\n";
      while (P<=end && A[P]<=pivot)
      { prompt("A[P]<=pivot, move P up");
        P+=1;
        number_of_operations+=1;
        display(A, start, end, P, Q, pivot); }
      cout << "phase b: move Q down while A[Q] >= pivot\n";
      while (Q>=start && A[Q]>=pivot)
      { prompt("A[Q]>=pivot, move Q down");
        Q-=1;
        number_of_operations+=1;
        display(A, start, end, P, Q, pivot); }
      if (P<Q)
      { prompt("A[P] and A[Q] are out of order, swap");
        exchange(A[P], A[Q]);
        P+=1;
        Q-=1;
        number_of_operations+=1;
        display(A, start, end, P, Q, pivot); }
      if (P==Q)
      { if (A[P]<=pivot)
        { prompt("one item left, <= pivot, move P up");
          number_of_operations+=1;
          P+=1; }
        else
        { prompt("one item left, >= pivot, move Q down");
          number_of_operations+=1;
          Q-=1; }
        display(A, start, end, P, Q, pivot);
        break; } }
    cout << "region " << start << " to " << end << " successfully partitioned about " << pivot << "\n";
    if (Q>start)
    { if (Q==end)
      { exchange(A[pivotpos], A[Q]);
        Q-=1; }
      cout << "remember to sort first partition, " << start << " to " << Q << "\n";
      agenda.add(task(A, start, Q)); }
    if (P<end)
    { if (P==start)
      { exchange(A[P], A[pivotpos]);
        P+=1; }
      cout << "remember to sort second partition, " << P << " to " << end << "\n";
      agenda.add(task(A, P, end)); } }
  cout << "No remaining tasks\n";
  cout << "N = " << size << " things sorted in " << number_of_operations << " operations.\n";
  cout << "N x log2(N) = " << int(size*log(size)/log(2.0)) << "\n"; }
      
void main(int argc, char * argv[])
{ int N;
  int * ARRAY;
  if (argc<=2)
  { if (argc==2)
      N=atol(argv[1]);
    else
    { cout << "How many numbers? ";
      cin >> N;
      string temp;
      getline(cin, temp); }
    ARRAY = new int [N];
    srandomdev();
    for (int i=0; i<N; i+=1)
      ARRAY[i] = random()%900 + 100; }
  else
  { N = argc-1;
    ARRAY = new int [N];
    for (int i=0; i<N; i+=1)
      ARRAY[i] = atol(argv[i+1]); }
  sort(ARRAY, N);
  cout << "Final sorted result\n";
  for (int i=0; i<N; i+=1)
    cout << ARRAY[i] << "\n"; }