爲什麼就地合併排序不穩定？

Question

下面的實現是穩定的，因爲它使用<=而不是<標記爲XXX的行。這也使得它更有效率。是否有理由在此行使用<而不是<=？

/** 
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

因爲在代碼中<=確保相同值元素（在排序陣列的左側和右側的一半）將不被交換。 而且，它避免了無用的交換。

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. 
    */ 
... 
} 

假定在這兩個半部相同的值元素（例如，「5」）和上述操作者<。 正如上面的評論所示，右邊的'5'將被插入在左邊的'5'之前，換句話說，相同的值元素將被交換。 這意味着排序不穩定。 而且，交換相同值的元素效率低下。

---

我想低效率的原因來自算法本身。 您的合併階段是使用插入排序實現的（如您所知，它是O（n^2））。

當你對巨大的數組進行排序時，你可能不得不重新實現。

Answer 2

到位穩定的排序最快知：
http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html