병합 정렬이 안정되지 않은 이유는 무엇입니까?

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