Mój algorytm sortowania scalania zajmuje zbyt dużo czasu na wprowadzanie dużych plików? - c ++, algorytm, złożoność czasowa, mergesort, divide-and-conquer

cóż, to nie jest dokładnie scalony sort, algorytmzlicza liczbę na inwersjach w tablicy używając sortowania scalonego (w zasadzie dodałem tylko jedną prostą linię) zajmuje 2.415 sekund, aby odczytać i scalić sortowanie 100 000 różnych liczb całkowitych z pliku tekstowego, podczas gdy inni, którzy rozwiązali ten sam problem (na stronie coursera.com), stwierdzili, że zajęło im to mniej niż 0,5 sekundy

tutaj jest mój kod, co poszło nie tak? Czytanie plików może? dzięki

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

}

Odpowiedzi:

Moim zdaniem jedną kwestią jest to, że w funkcji scalaniaalokujesz zbyt dużo miejsca, a kopia z powrotem zajmuje również O (N), co powoduje, że całkowity czas kopiowania O (N * N) zamiast O (N * Log (N)). Prosta zmiana funkcji scalania może wyglądać następująco:

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