Arrays.sort（Object [] a） - 它是如何實現的？

Question

有沒有關於Arrays.sort（Object [] a）使用的mergeSort的實現方式？雖然它被證明是相當不錯的，但我很難理解它（特別是爲什麼src和dest在mergeSort（）get遞歸調用時被切換）。

Answer 1

Here is the source的java.util.Arrays。

實際上，您在JDK中擁有該源代碼 - 只需在您的IDE中打開java.util.Arrays，並且會顯示源代碼+註釋。如果你沒有IDE，看看JDK_HOME\src.zip

然後，把它放在你的IDE中，並跟蹤它的工作原理。

• 放斷點（和調試模式運行程序）
• 使用它System.out.println(..)
• 改變部分看看它們是如何體現。
• 閱讀wikipedia article about merge sort
• 要注意此評論：// Recursively sort halves of dest into src

Answer 2

我曾經有過與你同樣的困惑。根據我的理解，這種切換的原因很簡單 - 使後續合併步驟更容易。沒有魔法。

private static void mergeSortWithoutSwitch(Object[] src, Object[] dest, int low, int high, int off) { 
    int length = high - low; 

    // Insertion sort on smallest arrays 
    if (length < INSERTIONSORT_THRESHOLD) { 
     for (int i = low; i < high; i++) 
      for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--) 
       swap(dest, j, j - 1); 
     return; 
    } 

    // Recursively sort halves of dest into src 
    int destLow = low; 
    int destHigh = high; 
    low += off; 
    high += off; 
    int mid = (low + high) >>> 1; 
    mergeSortWithoutSwitch(src, dest, low, mid, off); 
    mergeSortWithoutSwitch(src, dest, mid, high, off); 

    // If list is already sorted, just copy from src to dest. This is an 
    // optimization that results in faster sorts for nearly ordered lists. 
    if (((Comparable) dest[mid - 1]).compareTo(dest[mid]) <= 0) { 
     return; 
    } 

    // Merge sorted halves (now in src) into dest 
    for (int i = destLow, p = low, q = mid; i < destHigh; i++) { 
     if (q >= high || p < mid && ((Comparable) dest[p]).compareTo(dest[q]) <= 0) 
      src[i] = dest[p++]; 
     else 
      src[i] = dest[q++]; 
    } 

    // copy back 
    for (int i = destLow; i < destHigh; i++) { 
     dest[i] = src[i]; 
    } 

} 

上面是沒有切換的實現，從代碼中可以看到我們需要多一步合併 - 複製回來。我認爲mergeSort中的參數命名有點困惑，因爲src是隻用於合併步驟的輔助數組，所以最好用aux命名（我們甚至可以將它從方法簽名中移除，並創建一個局部變量合併時）。 dest是結果數組。