Heap Sort

void down(int* p,int k,int n)
{
    int l = k;
    int k1 = ((k+1)<<1) - 1;
    if(k1<n && p[k1]>p[l])
        l = k1;
    k1++;
    if(k1<n && p[k1]>p[l])
        l = k1;
    if(l!=k)
    {
        int t = p[l];p[l] = p[k];p[k] = t;
        down(p,l,n);
    }
}

void heapSort(int* p,int l)
{
    for(int i = (l<<2)-1;i>=0;--i)
        down(p,i,l);
    for(int i = l-1;i>0;--i)
    {
        int t = p[i];p[i] = p[0];p[0] = t;
        down(p,0,--l);
    }
}