Mengapa Collections.sort menggunakan Mergesort tetapi Arrays.sort tidak?

Saya menggunakan JDK-8 (x64). Untuk Arrays.sort(primitif) saya menemukan yang berikut ini di dokumentasi Java:

Algoritme pengurutannya adalah Dual-Pivot Quicksort oleh Vladimir Yaroslavskiy, Jon Bentley, dan Joshua Bloch.`

Untuk Collections.sort(objek) saya menemukan "Timsort" ini:

Implementasi ini adalah mergesort yang stabil, adaptif, dan berulang ... Implementasi ini membuang daftar yang ditentukan ke dalam larik, mengurutkan larik , dan mengulangi daftar yang menyetel ulang setiap elemen dari posisi yang sesuai dalam larik.

Jika Collections.sortmenggunakan array, mengapa tidak memanggil Arrays.sortatau menggunakan QuickSort pivot ganda ? Mengapa menggunakan Mergesort ?

API menjamin pengurutan stabil yang tidak ditawarkan Quicksort . Namun, saat mengurutkan nilai primitif berdasarkan urutan aslinya, Anda tidak akan melihat perbedaan karena nilai primitif tidak memiliki identitas. Oleh karena itu, Quicksort dapat digunakan untuk array primitif dan akan digunakan jika dianggap lebih efisien¹.

Untuk objek yang mungkin Anda perhatikan, ketika objek dengan identitas berbeda yang dianggap sama menurut equalsimplementasinya atau yang disediakan Comparatormengubah urutannya. Oleh karena itu, Quicksort bukanlah suatu pilihan. Jadi varian MergeSort digunakan, versi Java saat ini menggunakan TimSort . Ini berlaku untuk keduanya, Arrays.sortdan Collections.sort, meskipun dengan Java 8, Listalgoritma itu sendiri dapat menimpa algoritme pengurutan.

¹ Keuntungan efisiensi Quicksort adalah membutuhkan lebih sedikit memori saat dilakukan di tempat. Tetapi ini memiliki kinerja kasus terburuk yang dramatis dan tidak dapat mengeksploitasi proses data yang telah diurutkan sebelumnya dalam array, yang dilakukan oleh TimSort .

Oleh karena itu, algoritme pengurutan dikerjakan ulang dari versi ke versi, sambil tetap berada di kelas dengan nama yang sekarang menyesatkan DualPivotQuicksort. Selain itu, dokumentasi tidak sesuai, yang menunjukkan, bahwa secara umum adalah ide yang buruk, untuk menyebutkan algoritme yang digunakan secara internal dalam spesifikasi, jika tidak diperlukan.

Situasi saat ini (termasuk Java 8 hingga Java 11) adalah sebagai berikut:

• Umumnya, metode pengurutan untuk array primitif hanya akan menggunakan Quicksort dalam keadaan tertentu. Untuk array yang lebih besar, mereka akan mencoba mengidentifikasi proses data yang telah diurutkan terlebih dahulu, seperti yang dilakukan TimSort , dan akan menggabungkannya ketika jumlah proses tidak melebihi ambang tertentu. Jika tidak, mereka akan kembali ke Quicksort , tetapi dengan implementasi yang akan kembali ke jenis Penyisipan untuk rentang kecil, yang tidak hanya memengaruhi larik kecil, tetapi juga rekursi pengurutan cepat.
• sort(char[],…)dan sort(short[],…)tambahkan kasus khusus lainnya, untuk menggunakan Sortir penghitungan untuk array yang panjangnya melebihi ambang tertentu
• Demikian juga, sort(byte[],…)akan menggunakan jenis Penghitungan , tetapi dengan ambang yang jauh lebih kecil, yang menciptakan kontras terbesar dengan dokumentasi, karena sort(byte[],…)tidak pernah menggunakan Quicksort. Ini hanya menggunakan semacam penyisipan untuk larik kecil dan jenis Penghitungan sebaliknya.

Saya tidak tahu tentang dokumentasinya, tetapi implementasi java.util.Collections#sortdi Java 8 (HotSpot) berjalan seperti ini:

@SuppressWarnings({"unchecked", "rawtypes"})
public static <T> void sort(List<T> list, Comparator<? super T> c) {
    list.sort(c);
}

Dan List#sortimplementasi ini:

@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

Jadi, pada akhirnya, Collections#sortmenggunakan Arrays#sort(dari elemen objek) di belakang layar. Implementasi ini menggunakan merge sort atau tim sort.

Menurut Javadoc, hanya array primitif yang diurutkan menggunakan Quicksort. Larik objek juga diurutkan dengan Mergesort.

Jadi Collections.sort tampaknya menggunakan algoritme pengurutan yang sama seperti Arrays.sort untuk Objek.

Pertanyaan lain adalah mengapa algoritma pengurutan yang berbeda digunakan untuk array primitif daripada untuk array Object?

Seperti yang dinyatakan di banyak jawaban.

Quicksort digunakan oleh Arrays.sort untuk menyortir koleksi primitif karena stabilitas tidak diperlukan (Anda tidak akan tahu atau peduli jika dua int identik ditukar dalam pengurutan)

MergeSort atau lebih spesifik Timsort digunakan oleh Arrays.sort untuk mengurutkan koleksi objek. Stabilitas diperlukan. Quicksort tidak memberikan stabilitas, Timsort menyediakannya.

Collections.sort mendelegasikan ke Arrays.sort, itulah sebabnya Anda melihat javadoc mereferensikan MergeSort.

Quick Sort memiliki dua kelemahan utama dalam hal merge sort:

• Itu tidak stabil jika menyangkut non primitif.
• Itu tidak menjamin kinerja n log n.

Stabilitas bukanlah masalah untuk tipe primitif, karena tidak ada gagasan tentang identitas yang berbeda dari persamaan (nilai).

Stabilitas adalah masalah besar saat menyortir objek arbitrer. Ini adalah keuntungan sampingan yang bagus bahwa Merge Sort menjamin n log n (waktu) kinerja apapun inputnya. Itulah mengapa merge sort dipilih untuk menyediakan pengurutan yang stabil (Merge Sort) untuk mengurutkan referensi objek.