Arrays.sort (Object [] a) - come viene implementato?

Question

Esistono risorse su come viene implementato il mergeSort utilizzato da Arrays.sort (Object [] a)? Sebbene sia documentato abbastanza bene, ho difficoltà a comprenderlo (specialmente perché src e dest sono cambiati quando mergeSort() get viene chiamato ricorsivamente).

Answer 1

Here is the source di java.util.Arrays.

In realtà, si dispone di quel codice sorgente nel JDK - basta aprire java.util.Arrays nel proprio IDE e il codice sorgente + i commenti appariranno. Se non hai un IDE, guarda JDK_HOME\src.zip

Quindi, mettilo nel tuo IDE e traccia come funziona.

• put punti di interruzione (ed eseguire un programma in modalità debug)
• uso System.out.println(..)
• sostituzione di parti di esso per vedere come si riflettono.
• leggere il prestare attenzione wikipedia article about merge sort
• a questo commento: // Recursively sort halves of dest into src

Answer 2

ho mai avuto la stessa confusione con voi. Secondo la mia comprensione, la ragione di questo passaggio è molto semplice: semplificare la procedura di fusione. Nessuna magia

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

} 

è al di sopra l'attuazione senza passare, dal codice, si può vedere abbiamo bisogno di più di un passo nella fusione - copiare indietro. Penso che la denominazione dei parametri in mergeSort sia un po 'confusa, dato che src è un array ausiliario che viene utilizzato solo in fase di unione, sarà meglio chiamarlo con aux (possiamo anche rimuoverlo dalla firma del metodo e creare una variabile locale durante la fusione). E dest è la matrice dei risultati.