Mengapa algoritma quicksort rekursif saya memiliki partisi yang miring?

Saya telah menerapkan algoritma quicksort di C++. Namun, algoritma saya berjalan jauh lebih lambat daripada algoritma mergesort saya. Ini berjalan jauh lebih cepat pada array terbalik tetapi selain itu dibutuhkan waktu sekitar empat atau lima kali lebih lama.

Algoritme saya menggunakan rekursi, meskipun menurut saya bukan itu masalahnya. Saya telah mencoba beralih ke pivot acak alih-alih median dari tiga pilihan pivot. Itu bahkan lebih lambat.

Termasuk:

#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<iostream>

unsigned int recurse(int*a,unsigned int length)
{
    int value=0;
    unsigned int depth=0;
    if(length<=1)
    {
        depth=1;
    }
    else if(length==2)
    {
        if(a[0]>a[1])
        {
            value=a[0];
            a[0]=a[1];
            a[1]=value;
        }
        depth=1;
    }
    else if(length==3)
    {
        if(a[0]>a[1])
        {
            value=a[0];
            a[0]=a[1];
            a[1]=value;
        }
        if(a[0]>a[2])
        {
            value=a[0];
            a[0]=a[2];
            a[2]=value;
        }
        if(a[1]>a[2])
        {
            value=a[1];
            a[1]=a[2];
            a[2]=value;
        }
        depth=1;
    }
    else
    {
        //unsigned int fifth=(length>>3)+(length>>4)+(length>>6);
        unsigned int middle=length>>1;
        unsigned int choices[5]={0,middle>>1,middle,middle+(middle>>1),length-1};
        unsigned int left=0;
        unsigned int right=length-1;
        unsigned int index=0;
        for(unsigned int i=0;i<4;i++)
        {
            index=i;
            while(a[choices[index]]>a[choices[index+1]])
            {
                value=a[choices[index]];
                a[choices[index]]=a[choices[index+1]];
                a[choices[index+1]]=value;
                if(index>0)
                {
                    index--;
                }
            }
        }
        while(right>left)
        {
            while((a[++left]<=a[middle])&&right>left);
            while((a[--right]>=a[middle])&&right>left);
            if(right>left)
            {
                value=a[left];
                a[left]=a[right];
                a[right]=value;
            }
        }
        value=a[middle];
        if(left<middle&&right<middle)
        {
            a[middle]=a[left];
            a[left]=value;
            middle=left;
        }
        else if(left>middle&&right>middle)
        {
            a[middle]=a[left-1];
            a[left-1]=value;
            middle=left-1;
        }
        long double y;
        x++;
        ratio+=y=fabs((long double)(length>>1)-(long double)middle)/length;
        if(length>=1048576)
        {
            cout<<middle<<" "<<length<<" "<<y<<endl;
        }
        depth=max(recurse(a,middle),recurse(a+middle+1,length-middle-1))+1;
    }
    return depth;
}

Kedalamannya hanya untuk menghitung kedalaman rekursi. Saya mencoba melihat apakah itu masalahnya.

int main(int argl,char**argv)
{
    unsigned int length=0;
    cin>>length;
    cout<<length<<endl;
    int*numbers=new int[length];
    for(unsigned int i=0;i<length;i++)
    {
        numbers[i]=(int)rand()%(length<<1);
    }
    time_t start=time(0);
    mergesort(numbers,length);
    time_t end=time(0);
    cout<<end-start<<endl;
    for(unsigned int i=0;i<length;i++)
    {
        numbers[i]=(int)rand()%(length<<1);
    }
    start=time(0);
    unsigned int depth=recurse(numbers,length);
    end=time(0);
    cout<<end-start<<endl;
    cout<<"Depth: "<<depth<<endl;
    return 0;
}

Sunting: Kode untuk pengurutan gabungan, seperti yang diminta:

void mergesort(int*a,unsigned int length)
{
    if(length<=1)
    {
        return;
    }
    else if(length==2)
    {
        if(a[0]>a[1])
        {
            int value=a[0];
            a[0]=a[1];
            a[1]=value;
        }
    }
    else
    {
        unsigned int index1=0,index2=0;
        unsigned int divide1=1,divide2=1;
        unsigned int merge=2;
        unsigned int start=0;
        int*b=new int[length];
        while(merge<=length)
        {
            while(index1<divide1&&index2<divide2)
            {
                if(a[start+index1]>a[start+divide1+index2])
                {
                    b[start+index1+index2]=a[start+divide1+index2++];
                }
                else
                {
                    b[start+index1+index2]=a[start+index1++];
                }
            }
            if(index1<divide1)
            {
                for(unsigned int i=index1;index1<divide1;index1++)
                {
                    b[start+index1+index2]=a[start+index1];
                }
            }
            else
            {
                for(unsigned int i=index2;index2<divide2;index2++)
                {
                    b[start+index1+index2]=a[start+divide1+index2];
                }
            }
            if(start+merge>=length)
            {
                if(start==0)
                {
                    merge<<=1;
                }
                else
                {
                    start=0;
                    index1=0;
                    index2=0;
                    divide1=merge;
                    divide2=merge<<1>length?length-divide1:merge;
                    merge=divide1+divide2;
                }
                for(unsigned int i=0;i<length;i++)
                {
                    a[i]=b[i];
                }
            }
            else
            {
                start+=merge;
                index1=0;
                index2=0;
                divide1=start+divide1>length?length-start:divide1;
                divide2=start+merge>length?max((int)(length-(start+divide1)),0):divide2;
            }
        }
    }
}

Hasilnya, untuk nomor 33554432: Edit, ubah kode saya, perbarui hasil:

33554432
33554432
8
22
Depth: 765
0.4437349830864823

Angka terakhir adalah jarak rata-rata poros dari tengah. Hampir 0,45, hampir selisih satu banding dua puluh.