大きなファイル入力にマージソートアルゴリズムが長すぎますか？

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

1つの問題は、代わりにマージ機能では、あなたはあまりにも多くのスペースを割り当て、コピーバックも総コピー時間O（N * N）を作る非常にO（N）を取るということですO（N * Log（N））のうちの1つである。マージ機能への簡単な変更は次のようになります。

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