Почему в месте слияния сортировка нестабильна?

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