Arrays. sort 소스 코드 분석

업무 중 에 원본 코드 를 잘 보지 않 기 때문에 많은 문제 들 이 깊이 연구 되 지 않 았 을 것 이다.향상 이 필요 하기 때문에 우수한 사람 이 쓴 코드 를 알 아 볼 수 있어 야 합 니 다. 그래서 저 는 JDK 소스 코드 부터 시작 해서 소스 코드 를 볼 때 블 로그 방식 으로 기록 합 니 다!
(이 소스 코드 는 JDK 1.8 버 전 을 기반 으로 낮은 버 전과 큰 차이 가 있 음)
1. Arrays. sort 방법 안내

Sorts the specified range of the specified array of objects according to the order induced by the specified comparator. 
The range to be sorted extends from index fromIndex, inclusive, to index toIndex, exclusive. 
(If fromIndex==toIndex, the range to be sorted is empty.) 
All elements in the range must be mutually comparable by the specified comparator 
(that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

 This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.
Implementation note: This implementation is a stable, adaptive, 
iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, 
while offering the performance of a traditional mergesort when the input array is randomly ordered. 
If the input array is nearly sorted, the implementation requires approximately(   ;  ) n comparisons. 
Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.
The implementation takes equal advantage of ascending and descending order in its input array, 
and can take advantage of ascending and descending order in different parts of the the same input array. 
It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array. 

       이상 은 대체적으로 다음 과 같은 몇 가지 정 보 를 말 했다.
        1. 정렬 된 요 소 는 Comparable 인 터 페 이 스 를 실현 해 야 합 니 다. 프로그램 에서 compare 방법 을 실행 할 때 ClassCastException 이상 을 해 서 는 안 됩 니 다.
        2. 같은 요 소 는 정렬 작업 을 하지 않 습 니 다.
        3. 방법 에서 병합 정렬 방식 으로 정렬 했 습 니 다. 배열 의 일부 질서 있 는 상 태 는 nlg (n) 차 비교 가 필요 합 니 다.
        4. 배열 의 데이터 가 기본적으로 질서 있 는 상태 에 있 을 때 n 번 정도 비교 해 야 합 니 다.
2. 소스 코드 해독
    2.1 입구 방법 sort

public static  void sort(T[] a, int fromIndex, int toIndex, Comparator super T> c) {
        //         
        if (c == null) {
            sort(a, fromIndex, toIndex);
        } else {
            rangeCheck(a.length, fromIndex, toIndex);
            //      ，LegacyMergeSort 1.8          ，          ,
            //   ，      
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, fromIndex, toIndex, c);
            else
                //               
                TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
        }
    }

    2.2 Comparator 가 설정 되 어 있 지 않 음

public static void sort(Object[] a, int fromIndex, int toIndex) {
        //              
        rangeCheck(a.length, fromIndex, toIndex);
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, fromIndex, toIndex);
        else
            ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
    }

//       ，      ，     
private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException(
                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException(fromIndex);
        }
        if (toIndex > arrayLength) {
            throw new ArrayIndexOutOfBoundsException(toIndex);
        }
    }

sort 방법 을 통 해 알 수 있 듯 이 사용자 정의 Comparator 가 지정 되 지 않 았 을 때 실제 ComparableTimsert 방법 을 실행 하 는 정적 방법 입 니 다. 다음 과 같은 방법 으로 구체 적 으로 어떤 일 을 했 는 지 살 펴 보 겠 습 니 다.

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
        //           ，assert     
        assert a != null && lo >= 0 && lo <= hi && hi <= a.length;
        
        //          
        int nRemaining  = hi - lo;

        //         2，       ，    
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted

        // If array is small, do a "mini-TimSort" with no merges
        //   ,MIN_MERGE=32,      ，               
        //         ，            
        if (nRemaining < MIN_MERGE) {
            //              ，                      
            int initRunLen = countRunAndMakeAscending(a, lo, hi);
            binarySort(a, lo, hi, lo + initRunLen);
            return;
        }

        /**
         * March over the array once, left to right, finding natural runs,
         * extending short natural runs to minRun elements, and merging runs
         * to maintain stack invariant.
         */
        //             
        ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
        
        //            ，   ，     32    ，      ,
        //         16 <= k <= 32  
        int minRun = minRunLength(nRemaining);
        do {
            // Identify next run
            //           
            int runLen = countRunAndMakeAscending(a, lo, hi);            
            // If run is short, extend to min(minRun, nRemaining)
            //         ?         ，         ，         
            //   runLen == mainRun   ，                  
            if (runLen < minRun) {                
                int force = nRemaining <= minRun ? nRemaining : minRun;
                //   ,     ，lo     ,force        ，  lo+runLen             
                //   lo + force    ，       
                binarySort(a, lo, lo + force, lo + runLen);
                runLen = force;            
            }   
            // Push run onto pending-run stack, and maybe merge
            //     ，     
            ts.pushRun(lo, runLen);            
            ts.mergeCollapse();            
            // Advance to find next run            
            lo += runLen;            
            nRemaining -= runLen;        
        } while (nRemaining != 0);        
        // Merge all remaining runs to complete sort        
        assert lo == hi;        
        ts.mergeForceCollapse();        
        assert ts.stackSize == 1;    
    } 

다음은 프로그램 에서 질서 있 는 하위 배열 의 길 이 를 어떻게 판단 하 는 지 살 펴 보 겠 습 니 다.

/**
* lo:           
* hi:          
*/
private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
        assert lo < hi;
        int runHi = lo + 1;
        if (runHi == hi)
            return 1;

        // Find end of run, and reverse range if descending
        //      ，         Comparator   ，         Comparable  
        //      comparaTo            ,              comparable  
        //            lo + 1  ，  lo + 1       ，              ，  
        //            ，          
        if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
            while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
                runHi++;
            //        
            reverseRange(a, lo, runHi);
        } else {                              // Ascending
            while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
                runHi++;
        }
        //              -     ,          
        return runHi - lo;
    }

위의 방법 에서 주로 두 가 지 를 실현 했다.
    1. 아래 표 시 를 시작 할 때 정렬 해 야 할 배열 을 검색 합 니 다. 내림차 순 으로 배열 하면 질서 있 는 하위 배열 이 끝 날 때의 아래 표 시 를 runHi + + 로 계산 하고 내림차 순 하위 배열 을 오름차 순 으로 반전 합 니 다.
    2. 오름차 서브 배열 이 라면 질서 있 는 부분 끝 요소 의 아래 표 시 를 계산 합 니 다.
다음은 반전 의 실현 을 간단하게 살 펴 보 자.

private static void reverseRange(Object[] a, int lo, int hi) {
        hi--;
        while (lo < hi) {
            Object t = a[lo];
            a[lo++] = a[hi];
            a[hi--] = t;
        }
    }

원본 코드 를 보면 배열 의 요소 의 앞 뒤 를 교환 하여 이 루어 진 다 는 것 을 알 수 있 습 니 다.
마지막 으로 정렬 을 실현 하 는 방법 으로 소스 코드 를 실현 하 는 것 이다.

/**
*   a:        
*   lo:        
*   hi:      
*   start:            
*/
private static void binarySort(Object[] a, int lo, int hi, int start) {
        assert lo <= start && start <= hi;
        if (start == lo)
            start++;
        for ( ; start < hi; start++) {
            //            
            Comparable pivot = (Comparable) a[start];

            // Set left (and right) to the index where a[start] (pivot) belongs
            //          
            int left = lo;
            //          
            int right = start;
            assert left <= right;
            /*
             * Invariants:
             *   pivot >= all in [lo, left).
             *   pivot <  all in [right, start).
             */
            //                ，          pivot    
            //           
            while (left < right) {
                //        ， left   right        ,
                //   (left + right) / 2              
                int mid = (left + right) >>> 1;
                //                 ，
                //      pivot       ，  right          
                //    ？          start  ，                ，      
                //         ，     
                if (pivot.compareTo(a[mid]) < 0)
                    right = mid;
                else
                    left = mid + 1;
            }
            assert left == right;

            /*
             * The invariants still hold: pivot >= all in [lo, left) and
             * pivot < all in [left, start), so pivot belongs at left.  Note
             * that if there are elements equal to pivot, left points to the
             * first slot after them -- that's why this sort is stable.
             * Slide elements over to make room for pivot.
             */
            int n = start - left;  // The number of elements to move
            // Switch is just an optimization for arraycopy in default case
            switch (n) {
                case 2:  a[left + 2] = a[left + 1];
                case 1:  a[left + 1] = a[left];
                         break;
                default: System.arraycopy(a, left, a, left + 1, n);
            }
            a[left] = pivot;
        }
    }

요약:
    1. 배열 길이 < 32 비트 시 정렬
    2. 배열 길이 > 32 시 계 산 된 세그먼트 배열 길이 에 따라 배열 을 작은 블록 으로 나 눈 다음 작은 블록 마다 정렬 을 마 친 후 결 과 를 합 친다.
이상 은 단지 나의 개인 적 인 견해 일 뿐 이 니, 비판 과 지적 을 바 랍 니 다!