#define eq(A,B) (!less(A,B)&& !less(B,A))

void quicksort(Item a[],int l,int r)
{
    int i,j,k,p,q;
    Item v;
    
    if (r <=l) return;
    
    v=a[r];
    i=l-1;
    j=r;
    p=l-1;
    q=r;

    for(;;) {
        while (less(a[++i],v));
        
        while (less(v,a[--j]))
            if (j==l) break;

        if (i>=j) break;

        exch(a[i],a[j]);
        if (eq(a[i],v)) {
            p++;
            exch(a[p],a[i]);
        }
        
        if (eq(v,a[j])) {
            q--;
            exch(a[q],a[j]);
        }
    }
    exch(a[i],a[r]);
    
    j=i-1;
    i=i+1;

    for (k=l ; k<p;k++,j++)
        exch(a[k],a[j]);

    for (k=r-1;k>q;k--,i++)
        exch(a[k],a[i]);

    quicksort(a,l,j);
    quicksort(a,i,r);
}