Python DSALesson 111Preview gratis
Merge Sort
Lesson ini bagian dari Python · Semua level
Ringkasan
Pelajaran ini membahas Merge Sort, algoritma divide and conquer yang membagi list menjadi dua bagian secara rekursif sampai berukuran satu, lalu menggabungkannya kembali dalam keadaan terurut. Merge sort konsisten O(n log n) pada semua kasus sehingga sering dipakai untuk data berukuran besar. Kelemahannya adalah memerlukan memori tambahan untuk array sementara saat penggabungan.
Poin kunci
- Tahapan merge sort: split list menjadi dua, urutkan masing-masing secara rekursif, lalu merge.
- Fungsi merge menggabungkan dua list terurut menjadi satu list terurut dengan membandingkan elemen terdepan.
- Kompleksitas O(n log n) pada kasus terbaik, rata-rata, maupun terburuk.
- Merge sort stabil karena elemen sama dipertahankan urutannya saat digabung.
- Membutuhkan memori tambahan O(n) sehingga tidak sepenuhnya in-place.
Materi lengkap
Contoh kode dan kuis
Materi lengkap, contoh kode, dan kuis tersedia untuk pelanggan. 5 soal.