Arrays.sort() - due diverse strategie per i tipi di dati primitivi e complessi da ordinare

Question

Arrays ordina i tipi di dati primitivi utilizzando il metodo DualPivotQuicksort, e i tipi complessi separatamente - utilizzando merge-sort. (inserimento-ordinamento se la dimensione dell'input è piccola).

DualPivotQuicksort utilizza ancora merge-sort su input di grandi dimensioni, tuttavia utilizza dual-quicksort su un intervallo di dimensioni di input più piccole.

Quello che mi chiedo è ... perché questa differenza nelle strategie nell'ordinamento dei tipi primitivi e non primitivi?

Le prestazioni dell'algoritmo dipendono in modo significativo dalla dimensione dell'input, non dai tipi di dati. Invocare il compareTo() anziché il confronto di grandezza normale sui primitivi (>, <, ==) non brucia spazio extra in memoria (e quindi non rallenta le prestazioni in termini assoluti a causa dello spazio di memoria) che sarebbe considerevole durante l'esecuzione.

Perché i metodi Arrays.sort() utilizzano strategie di ordinamento diverse per i tipi di dati primitivi, e per i tipi di dati complessi?

TIA.

Answer 1

Poiché i tipi di riferimento di ordinamento sono garantiti da stable, mentre non è necessario che le primitive di ordinamento siano (quindi è possibile utilizzare quicksort, un algoritmo di ordinamento non stabile, l'unire ordinamento invece è stabile). Si noti inoltre che quicksort is generally more optimal than mergesort (vedere this), che spiega il motivo per cui si è avvantaggiato nell'ordinamento delle primitive.

Da Arrays.sort:

Questo tipo è garantito per essere stabili: elementi uguali non saranno riordinate come risultato del genere.