///////    File: mysort.C    ///////
#include        <iostream.h>
#include        <stdlib.h>
#include        "TextLines.h"
#include        "SortKey.h"

int partition(TextLines& txtobj, int l, int r)
{   register int i,j;
    String piv;
    extern SortKey sortkey;
    i=l;  j=r;
// choose middle element as pivot
    txtobj.swap((i+j)/2,j);
    piv = txtobj[j];       // overloaded []
    while (i < j)
    {    while (sortkey.cmp(txtobj[i], piv) <= 0 && i < j) i++;
         while(j > i && sortkey.cmp(txtobj[j], piv) >= 0) j--;
         if (i < j) txtobj.swap(i++,j);
    }
    if (i != r) txtobj.swap(i,r);
    return(i);
}

void quicksort(TextLines& txtobj, int l, int r)
{   int k;
    if ( l >= r || l < 0 || r < 0)  return;
    k = partition (txtobj, l, r);
    quicksort(txtobj, l, k-1);
    quicksort(txtobj, k+1, r);
}

SortKey sortkey;   // default global sort key

main(int argc, String argv[])
{    if (argc > 2)
     {   cerr << "Usage: " << argv[0] << " key_position\n";
         exit(1);
     }
     if (argc == 2)
         sortkey = SortKey(atoi(argv[1]));
     TextLines txtobj;
     txtobj.input(cin);
     quicksort(txtobj,0,txtobj.length()-1);
     txtobj.display();
}