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是结果数组。