Arrays.sort (Object [] a) - comment est-il implémenté?

Question

Existe-t-il des ressources sur la façon dont le mergeSort utilisé par Arrays.sort (Object [] a) est implémenté? Bien que cela soit assez bien documenté, j'ai du mal à le comprendre (surtout pourquoi le src et le dest sont commutés quand mergeSort() est appelé récursivement).

Answer 1

Here is the source de java.util.Arrays.

En fait, vous avez ce code source dans le JDK - il suffit d'ouvrir java.util.Arrays dans votre IDE et le code source + les commentaires apparaîtront. Si vous n'avez pas d'IDE, regardez JDK_HOME\src.zip

Ensuite, placez-le dans votre IDE et tracez son fonctionnement.

• points d'arrêt de vente (et exécuter un programme en mode débogage)
• utilisation System.out.println(..)
• pièces de changement de celui-ci pour voir comment ils sont pris en compte.
• lire le wikipedia article about merge sort
• attention à ce commentaire: // Recursively sort halves of dest into src

Answer 2

j'ai jamais eu la même confusion avec vous. Selon ma compréhension, la raison de cette commutation est très simple - faire l'étape de fusion suivie plus facile. Pas de magie.

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]; 
    } 

} 

est supérieure à la mise en œuvre sans commutation, à partir du code, vous pouvez voir nous avons besoin d'une étape supplémentaire dans la fusion - copie en arrière. Je pense que le nom de paramètre dans mergeSort est un peu confus, puisque le src est un tableau auxiliaire qui est seulement utilisé dans l'étape de fusion, il vaudra mieux le nommer avec aux (Nous pouvons même le supprimer de la signature de la méthode et créer une variable locale lors de la fusion). Et dest est le tableau des résultats.