TimSort의 병합 정렬 알고리즘 최적화 및 Java 구현 깊이 탐구

소개
MergeSort는 이미 역방향으로 정렬된 순서에 대한 입력의 복잡도는 O(n^2)이고,timsort는 이러한 상황을 겨냥하여 MergeSort를 최적화하여 발생한 것으로 평균 복잡도는 n*O(logn)이며, 가장 좋은 상황은 O(n), 최악의 경우 n*O(logn)이다.또한 TimSort는 안정적인 정렬입니다.사상은 먼저 정렬열을 구분한 다음에 구역을 통합하는 것이다. 보기에는 Merge Sort 절차와 같지만 그 중에서 일부 역방향과 대규모 데이터에 대한 최적화 처리가 있다.
병합 정렬의 최적화 사상
병합 정렬에는 다음과 같은 몇 가지 최적화 방법이 있습니다.
빠른 정렬과 마찬가지로 소수조에 대해서는 삽입 정렬을 사용하거나 정렬을 선택하여 귀속 호출을 피할 수 있습니다.
merge () 를 호출하기 전에 a[mid]가 a[mid+1]보다 작은지 판단할 수 있습니다.만약 그렇다면 병합할 필요가 없다. 수조는 이미 질서정연하다.원인은 매우 간단하다. 두 개의 서브 그룹이 이미 질서정연해졌기 때문에 a[mid]는 첫 번째 서브 그룹의 최대치이고, a[mid+1]는 두 번째 서브 그룹의 최소치이다.a[mid]<=a[mid+1]일 때, 수조는 전체적으로 질서정연하다.
원소를 보조 수조로 복제하는 시간을 절약하기 위해 귀속 호출된 모든 차원에서 원시 수조와 보조 수조의 역할을 교환할 수 있다.
merge () 방법에서의 합병 과정은 i와 j가 경계를 넘었는지, 즉 어느 한쪽이 이미 다 썼는지 판단해야 한다.다른 방식으로 어느 한쪽이 이미 다 썼는지 검사하는 코드를 제거할 수 있다.구체적인 절차는 수조 a[]의 뒷부분을 내림차순으로 aux[]로 복사한 다음에 양쪽에서 합치는 것이다.수조 {1,2,3}와 {2,3,5}에 대해 첫 번째 하위 수조는 평소대로 복제하고 두 번째는 뒤에서 앞으로 복제한다. 최종aux[]의 요소는 {1,2,3,5,3,2}이다.이런 방법의 단점은 병합 정렬을 불안정한 정렬로 바꾸는 것이다.코드는 다음과 같습니다.

void merge(int[] a, int lo, int mid, int hi, int[] aux) {
for (int k = lo; k <= mid; k++) {
  aux[k] = a[k];
}
for (int k = mid + 1;k <= hi; k++) {
  aux[k] = a[hi - k + mid + 1];
}
int i = lo, j = hi;   // 
for (int k = lo; k <= hi; k++)
  if (aux[i] <= aux[j]) a[k] = aux[i++];
  else a[k] = aux[j--];
}

TimSort 단계
파티션
구역의 사상은 한 차례의 수조를 스캔하여 연속적인 정렬(승차 정렬이라면 정렬은 승차 정렬)이나 [엄격](정렬 알고리즘의 안정성을 확보)의 반열열을 하나의 구역(run)으로 하고 반열이라면 구역의 원소를 반전시키는 것이다.예:
1, 2, 3, 6, 4, 5, 8, 6, 4 구분 결과
[1,2,3,6],[4,5,8],[6,4]
그리고 반전 시퀀스
[1,2,3,6],[4,5,8],[4,6]
병합
극단적인 예를 들면 구역의 길이가 각각 10000, 101000, 10, 10이다. 우리는 당연히 10개의 10을 20, 20, 1000으로 합쳐서 1020이 되기를 바란다. 만약에 왼쪽에서 오른쪽 순서로 합치면 매번 10000이라는 수조와 작은 수조를 합치면 대가가 너무 크다.그래서 우리는 하나의 전략으로 합병의 순서를 최적화할 수 있다.
인스턴스
java의 Comparable TimSort.sort () 를 예로 들면 runstack을 사용하여 합병해야 하는지 확인하고,

    if (nRemaining < MIN_MERGE) {
      int initRunLen = countRunAndMakeAscending(a, lo, hi);
      binarySort(a, lo, hi, lo + initRunLen);
      return;
    }

IN 미만_MERGE(32) 정렬, 파티션 후 직접 2분으로 정렬 삽입

int minRun = minRunLength(nRemaining);
    do {
      // ， 
      int runLen = countRunAndMakeAscending(a, lo, hi);

      // run stack run minRun ， ， 
      if (runLen < minRun) {
        int force = nRemaining <= minRun ? nRemaining : minRun;
        binarySort(a, lo, lo + force, lo + runLen);
        runLen = force;
      }

      // run  run stack 
      ts.pushRun(lo, runLen);
      // ，i ， 
      //1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1] 
      //2. runLen[i - 2] > runLen[i - 1]
      ts.mergeCollapse();


      lo += runLen;
      nRemaining -= runLen;
    } while (nRemaining != 0);

    // Merge all remaining runs to complete sort
    assert lo == hi;
    // run
    ts.mergeForceCollapse();
    assert ts.stackSize == 1;

안에 있는 중요한 함수를 보고 있어요.

/**
*  2 run ， run run 
*  2 run ， 2 run 
*/
 private void mergeCollapse() {
    while (stackSize > 1) {
      int n = stackSize - 2;
      if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
        if (runLen[n - 1] < runLen[n + 1])
          n--;
        mergeAt(n);
      } else if (runLen[n] <= runLen[n + 1]) {
        mergeAt(n);
      } else {
        break; // Invariant is established
      }
    }
  }