三路归并排序

Question

我试图实现这个3路归并排序，但是这段代码不能输入超过4的大小，我一直无法找出问题所在，你能帮我吗？任何建议都会有帮助。

`#include<iostream>

void merge(int arr[],int start,int p1,int p2,int end);

void merge_sort(int arr[],int start, int end)
{
if(start>=end)
return;

if(end==start+1)
{
    if(arr[start]>arr[end])
    {
        int temp=arr[end];
        arr[end]=arr[start];
        arr[start]=temp;
    }
    return;
}

int size=end-start+1;
int p1=size/3;
int p2=2*p1;

merge_sort(arr,start,p1-1);
merge_sort(arr,p1,p2-1);
merge_sort(arr,p2,end);

merge(arr,start,p1,p2,end+1);
 }


 void merge(int arr[],int start,int p1,int p2,int end)
 {
int n=end-start;
int *temp=new int[n];

int j=start;
int k=p1;
int l=p2;
int i=0;

while(true)
{
    if(j==p1||k==p2||l==end)
    break;
    else
    if(arr[j]<arr[k]&&arr[j]<arr[l])
    {
        temp[i]=arr[j];
        j++;
    }
    else if(arr[k]<arr[j]&&arr[k]<arr[l])
    {
        temp[i]=arr[k];
        k++;
    }
    else
    {
        temp[i]=arr[l];
        l++;
    }
    i++;        
}

int r,s,limit_r,limit_s;

if(j==p1)
{
    r=k;
    s=l;
    limit_r=p2;
    limit_s=end;    
}
else if(k==p2)
{
    r=j;
    s=l;
    limit_r=p1;
    limit_s=end;
}
else if(l==end)
{
    r=j;
    s=k;
    limit_r=p1;
    limit_s=p2;
}

while(true)
{
    if(r==limit_r||s==limit_s)
    break;
    
    if(arr[r]<arr[s])
    {
        temp[i]=arr[r];
        r++;
    }
    else
    {
        temp[i]=arr[s];
        s++;
    }
    i++;
}

int final;

if(r==limit_r)
final=s;
else
final=r;

while(i<n)
{
    temp[i]=arr[final];
    final++;
    i++;
}

int test=start;

for(i=0;i<n;i++)
{
    arr[test]=temp[i];
    test++;
}

delete []temp;
return;
 }


  int main()
  {

int size;
std::cout<<"Enter the size of array:";
std::cin>>size;

int *mohit=new int[size];

std::cout<<"Enter the elements of the array:";

for(int m=0;m<size;m++)
std::cin>>mohit[m];

merge_sort(mohit,0,size-1);

std::cout<<"The final sorted array is:"<<std::endl;

for(int count=0;count<size;count++)
std::cout<<mohit[count]<<" ";

delete []mohit;

  }
 `

我尝试实现3路合并排序，但是对于较大的输入大小它失败了，我刚刚开始学习DSA，不知道在哪里发布这样的疑问，所以在这里吗？如果大家有什么解疑的平台可以推荐一下吗

Answer 1

问题是这一行正在做整数除法：

int p1 = size / 3;

它删除了数字的浮点部分，因此它可能在某个时刻被设置为 1，这使得

p2

的值永远等于 2。

要解决此问题，您可以将

p1

更改为浮点数，并使除法返回浮点数。您还必须将

p2

设置为分区的上限：

float p1 = size / 3.0;
int p2 = ceil(2 * p1);