我的合并排序算法对于大文件输入花费的时间太长？

Question

嗯，这不完全是合并排序，该算法使用合并排序计算数组中反转的次数（基本上我只是添加了一个简单的行）从一个文本文件中读取和合并排序 100,000 个不同的整数需要 2.415 秒，而解决相同问题的其他人（在 coursera.com 上）说他们用了不到 0.5 秒

这是我的代码，哪里出了问题？文件阅读也许？谢谢

#include <bits/stdc++.h>

using namespace std;
int a,b,i,j,n,x,k;
int t[100000]={0};
long long int s=0;

void merge(int a, int mid, int b)
     {
         i=a;
        j=mid+1;
        k=a;
        int v[100000]={0};
        while(i<=mid && j<= b)
        {
            if (t[i]<t[j])
                {v[k]=t[i];
                 i++;
                }
            else
            {v[k]=t[j];
             j++;
              s+=mid-i+1; //this line here counts the inversions
             }
           k++;
        }
       while(i<=mid)
        {v[k]=t[i];
         i++; k++;}

        while(j<=b)
        {v[k]=t[j];
         j++; k++;}

      for (i=a;i<k;i++)
         t[i]=v[i];
    }


void mergeSort(int a, int b)
    {
        if(a<b)
        {
           int mid=(a+b)/2;
            mergeSort(a,mid);
            mergeSort(mid+1,b);
            merge(a,mid,b);
        }
    }


int main(){
  ifstream fin("C:\Users\ASUS\Desktop\coursera.txt");
    n=100000;
    for(i=0;i<n;i++)
        fin>>t[i];

    mergeSort(0,n-1);

     cout<<endl<<s;

}

Answer 1

我能看到的一个问题是，在合并函数中，你分配了太多 space，并且复制回来也需要相当多的 O(N)，这使得总复制时间为 O(N * N)而不是 O(N*Log(N))。合并功能的简单更改可能是这样的：

void merge(int a, int mid, int b)
{
    i = a;
    j = mid + 1;
    k = 0;
    int* v = new int[b - a + 1];
    while (i <= mid && j <= b)
    {
        if (t[i]<t[j])
        {
            v[k] = t[i];
            i++;
        }
        else
        {
            v[k] = t[j];
            j++;
            s += mid - i + 1; //this line here counts the inversions
        }
        k++;
    }
    while (i <= mid)
    {
        v[k] = t[i];
        i++; k++;
    }

    while (j <= b)
    {
        v[k] = t[j];
        j++; k++;
    }

    for (i = 0; i<k; i++)
        t[a+i] = v[i];

    delete[] v;
    v = NULL;
}

我的合并排序算法对于大文件输入花费的时间太长？

My merge sort algorithm is taking too long for large file input?

c++

algorithm

mergesort

time-complexity

divide-and-conquer