เหตุใดอัลกอริทึมการเรียงลำดับแบบเรียกซ้ำของฉันจึงมีพาร์ติชันที่ไม่สมดุลเช่นนี้

ฉันได้ใช้อัลกอริธึมการเรียงลำดับอย่างรวดเร็วใน C ++ อย่างไรก็ตาม อัลกอริทึมของฉันทำงานช้ากว่าอัลกอริทึมการผสานของฉันมาก มันทำงานเร็วกว่ามากบนอาร์เรย์ที่กลับกัน แต่อย่างอื่นจะใช้เวลาประมาณสี่หรือห้าเท่า

อัลกอริทึมของฉันใช้การเรียกซ้ำ แม้ว่าฉันไม่คิดว่ามันเป็นปัญหาก็ตาม ฉันได้ลองสลับไปใช้เดือยแบบสุ่มแทนที่จะเป็นค่ามัธยฐานของตัวเลือกเดือยสามตัว นั่นยังช้ากว่าอีกด้วย

รวมถึง:

#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;
}

ความลึกมีไว้เพื่อการนับความลึกของการเรียกซ้ำเท่านั้น ฉันพยายามดูว่านั่นเป็นปัญหาหรือไม่

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;
}

แก้ไข: รหัสสำหรับการเรียงลำดับแบบผสานตามที่ร้องขอ:

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;
            }
        }
    }
}

ผลลัพธ์สำหรับหมายเลข 33554432: แก้ไข เปลี่ยนรหัสของฉัน อัปเดตผลลัพธ์:

33554432
33554432
8
22
Depth: 765
0.4437349830864823

ตัวเลขสุดท้ายคือระยะทางเฉลี่ยที่จุดหมุนอยู่ห่างจากจุดศูนย์กลาง อยู่ที่เกือบ 0.45 เกือบ 1 ถึง 20 แยก