Eventuali duplicati:
Why java Arrays use two different sort algorithms for different types?Java: Arrays.sort Quicksort e Mergesort
Così stavo leggendo l'Array doc sulle varie implementazioni di ordinamento. Quello che ho notato è che alcune delle implementazioni utilizzavano un quicksort sintonizzato mentre altre usavano un mergesort modificato. Perché la discrepanza?
Grazie!
Quicksort viene utilizzato per matrici di tipi primitivi mentre mergesort per matrici Object [].
Il motivo principale per cui Mergesort è utilizzato per gli oggetti che Mergesort è stabile - non riordinare gli elementi che sono uguali: http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
Per primitivi la stabilità del genere non ha senso, in quanto non è possibile distinguere due valori che sono pari. Quindi, quicksort viene utilizzato (tranne quando si ordina una matrice di oggetti, per la quale viene eseguito il mergesort). Inoltre, quicksort può essere eseguito, quindi non è necessario allocare un altro array.
Nel mondo di oggi, mergesort è diventato il sorter dominante, in quanto può essere implementato per utilizzare core multipli – ControlAltDel
, ma JDK non lo usa per ora. –
Detto questo, JDK 7 non usa più mergesort - utilizza il mitico [TimSort] (http://en.wikipedia.org/wiki/Timsort)! –
notato, grazie michael! – OckhamsRazor