我的合併排序算法對於大文件輸入花費的時間太長了？

Question

好吧，它不完全是一個合併排序，該算法使用合併排序（基本上我只是添加一條簡單的線）計數數組倒序數 它需要2.415秒來讀取和合並從一個文本文件排序100,000個不同的整數其他誰解決了同樣的問題（在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

一個問題，我可以看到的是，在合併功能，您分配了太多的空間，並且複製後面還需要相當長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; 
}