Mergesort-Implementierung ist langsam

Question

Ich mache einen Bericht über verschiedene Sortieralgorithmen in C++. Was mich verwirrt ist, dass mein Mergesort in beiden Sprachen langsamer als Heapsort zu sein scheint. Was ich gesehen habe ist, dass Heapsort langsamer sein soll.

mein Mergesort sortiert ein unsortiertes Array mit der Größe 100 000 mit einer Geschwindigkeit von 19,8 ms, während heapsort es bei 9,7 ms sortiert. Der Code für meine mergesort Funktion in C++ ist wie folgt:

void merge(int* array, int low, int mid, int high) 
{ 
int i, j, k; 
int lowLength = mid - low + 1; 
int highLength = high - mid; 


int* lowArray = new int[lowLength]; 
int* highArray = new int[highLength]; 

for (i = 0; i < lowLength; i++) 
    lowArray[i] = array[low + i]; 
for (j = 0; j < highLength; j++) 
    highArray[j] = array[mid + 1 + j]; 

i = 0; 
j = 0; 
k = low; 
while (i < lowLength && j < highLength) 
{ 
    if (lowArray[i] <= highArray[j]) 
    { 
     array[k] = lowArray[i]; 
     i++; 
    } 
    else 
    { 
     array[k] = highArray[j]; 
     j++; 
    } 
    k++; 
} 

while (i < lowLength) 
{ 
    array[k] = lowArray[i]; 
    i++; 
    k++; 
} 

while (j < highLength) 
{ 
    array[k] = highArray[j]; 
    j++; 
    k++; 
} 
} 

void mergeSort(int* array, int low, int high) 
{ 
if (low < high) 
{ 
    int mid = low + (high - low)/2; 

    mergeSort(array, low, mid); 
    mergeSort(array, mid + 1, high); 

    merge(array, low, mid, high); 
} 
} 

Answer 1

Das Beispiel Mergesort tut Zuordnung und Kopieren von Daten in merge(), und beide können mit einem effizienteren Mergesort beseitigt werden. Eine einzelne Zuweisung für das temp-Array kann in einer Hilfs-/Eintragsfunktion durchgeführt werden, und die Kopie wird vermieden, indem die Verschmelzungsrichtung abhängig von der Rekursionsstufe entweder durch Verwendung von zwei gegenseitig rekursiven Funktionen (wie im folgenden Beispiel) oder mit einem booleschen Wert geändert wird Parameter.

Hier ist ein Beispiel für eine C++ Top-Down-Merge-Sortierung, die einigermaßen optimiert ist. Eine Bottom-Up-Merge-Sortierung wäre etwas schneller, und bei einem System mit 16 Registern würde eine 4-Wege-Bottom-Merge-Sortierung noch etwas schneller erfolgen, etwa so schnell oder schneller als eine schnelle Sortierung.

// prototypes 
void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee); 
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee); 
void TopDownMerge(int a[], int b[], size_t ll, size_t rr, size_t ee); 

void MergeSort(int a[], size_t n)  // entry function 
{ 
    if(n < 2)       // if size < 2 return 
     return; 
    int *b = new int[n]; 
    TopDownSplitMergeAtoA(a, b, 0, n); 
    delete[] b; 
} 

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee) 
{ 
    if((ee - ll) == 1)     // if size == 1 return 
     return; 
    size_t rr = (ll + ee)>>1;   // midpoint, start of right half 
    TopDownSplitMergeAtoB(a, b, ll, rr); 
    TopDownSplitMergeAtoB(a, b, rr, ee); 
    TopDownMerge(b, a, ll, rr, ee);  // merge b to a 
} 

void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee) 
{ 
    if((ee - ll) == 1){     // if size == 1 copy a to b 
     b[ll] = a[ll]; 
     return; 
    } 
    size_t rr = (ll + ee)>>1;   // midpoint, start of right half 
    TopDownSplitMergeAtoA(a, b, ll, rr); 
    TopDownSplitMergeAtoA(a, b, rr, ee); 
    TopDownMerge(a, b, ll, rr, ee);  // merge a to b 
} 

void TopDownMerge(int a[], int b[], size_t ll, size_t rr, size_t ee) 
{ 
    size_t o = ll;      // b[]  index 
    size_t l = ll;      // a[] left index 
    size_t r = rr;      // a[] right index 
    while(1){       // merge data 
     if(a[l] <= a[r]){    // if a[l] <= a[r] 
      b[o++] = a[l++];   // copy a[l] 
      if(l < rr)     // if not end of left run 
       continue;    //  continue (back to while) 
      while(r < ee)    // else copy rest of right run 
       b[o++] = a[r++]; 
      break;      //  and return 
     } else {      // else a[l] > a[r] 
      b[o++] = a[r++];   // copy a[r] 
      if(r < ee)     // if not end of right run 
       continue;    //  continue (back to while) 
      while(l < rr)    // else copy rest of left run 
       b[o++] = a[l++]; 
      break;      //  and return 
     } 
    } 
}