Pourquoi le tri par fusion n'est pas stable?

Question

L'implémentation ci-dessous est stable car elle utilise <= au lieu de < sur la ligne marquée XXX. Cela le rend également plus efficace. Y at-il une raison d'utiliser < et non <= à cette ligne?

/** 
class for In place MergeSort 
**/ 
class MergeSortAlgorithm extends SortAlgorithm { 
    void sort(int a[], int lo0, int hi0) throws Exception { 
    int lo = lo0; 
    int hi = hi0; 
    pause(lo, hi); 
    if (lo >= hi) { 
     return; 
    } 
    int mid = (lo + hi)/2; 

     /* 
     * Partition the list into two lists and sort them recursively 
     */ 
     sort(a, lo, mid); 
     sort(a, mid + 1, hi); 

     /* 
     * Merge the two sorted lists 
     */ 
    int end_lo = mid; 
     int start_hi = mid + 1; 
    while ((lo <= end_lo) && (start_hi <= hi)) { 
      pause(lo); 
     if (stopRequested) { 
       return; 
      } 
      if (a[lo] <= a[start_hi]) {     // LINE XXX 
       lo++; 
      } else { 
       /* 
       * a[lo] >= a[start_hi] 
       * The next element comes from the second list, 
       * move the a[start_hi] element into the next 
       * position and shuffle all the other elements up. 
       */ 
     int T = a[start_hi]; 
       for (int k = start_hi - 1; k >= lo; k--) { 
        a[k+1] = a[k]; 
        pause(lo); 
       } 
       a[lo] = T; 
       lo++; 
       end_lo++; 
       start_hi++; 
      } 
     } 
    } 

    void sort(int a[]) throws Exception { 
    sort(a, 0, a.length-1); 
    } 
} 

Answer 1

Parce que le <= dans votre code assure que les éléments de même valeur (dans la moitié gauche et droite du tableau de tri) ne seront pas échangés. Et aussi, cela évite les échanges inutiles.

if (a[lo] <= a[start_hi]) { 
/* The left value is smaller than or equal to the right one, leave them as is. */ 
/* Especially, if the values are same, they won't be exchanged. */ 
lo++; 
} else { 
/* 
    * If the value in right-half is greater than that in left-half, 
    * insert the right one into just before the left one, i.e., they're exchanged. 
    */ 
... 
} 

On suppose que même élément à valeurs (par exemple, « 5 ») dans les deux moitiés et l'opérateur est au-dessus de <. Comme le montrent les commentaires ci-dessus, le "5" de droite sera inséré avant le "5" de gauche, en d'autres termes, les éléments de même valeur seront échangés. Cela signifie que le tri n'est pas stable. Et aussi, il est inefficace d'échanger des éléments de même valeur. Je suppose que la cause de l'inefficacité provient de l'algorithme lui-même. Votre étape de fusion est implémentée en utilisant le tri par insertion (comme vous le savez, c'est O (n^2)).

Vous devrez peut-être réimplémenter lorsque vous triez d'énormes tableaux.

Answer 2

connu le plus rapide en place tri stable:
http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html