Merge sort mengurutkan array dengan divide and conquer: belah array jadi dua, urutkan tiap separuh dengan cara yang sama, lalu gabungkan (merge) dua separuh yang sudah terurut. Langkah gabungnya mirip menyatukan dua tumpukan kartu yang sudah urut: bandingkan kartu paling atas di tiap tumpukan, ambil yang lebih kecil, ulangi.
🧪 Tebakan cepat: kamu mau menggabungkan
[27, 38, 43]dan[3, 9, 10, 82]jadi satu daftar urut. Angka pertama hasilnya cukup dicari di antara berapa angka: 2, 4, atau 7? Tebak dulu, jawabannya ada di bagian "Merge: menggabungkan dua daftar terurut".
Belah sampai tinggal satu, lalu gabungkan
Ini yang terjadi pada [38, 27, 43, 3, 9, 82, 10]:
| Langkah | Hasilnya |
|---|---|
| Divide | [38, 27, 43] [3, 9, 82, 10] |
| Divide | [38] [27, 43] [3, 9] [82, 10] |
| Divide | [38] [27] [43] [3] [9] [82] [10] |
| Merge | [38] [27, 43] [3, 9] [10, 82] |
| Merge | [27, 38, 43] [3, 9, 10, 82] |
| Merge | [3, 9, 10, 27, 38, 43, 82] |
mergeSort memanggil dirinya sendiri untuk tiap separuh (rekursi). Supaya berhenti, ada base case: array berisi 0 atau 1 angka pasti sudah terurut, jadi langsung dikembalikan.
function mergeSort(arr) {
if (arr.length <= 1) return arr; // base case: 1 angka pasti terurut
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
return [...result, ...left.slice(i), ...right.slice(j)];
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]
midadalah index tengah. Untuk 7 angka,Math.floor(7 / 2)hasilnya 3.arr.slice(0, mid)mengambil index 0 sampai sebelum 3 ([38, 27, 43]),arr.slice(mid)mengambil sisanya ([3, 9, 82, 10]).slicebikin array baru, array aslinya gak berubah.- Tiap separuh diurutkan dengan memanggil
mergeSortlagi, lalumergemenyatukan hasilnya. Dua function ini harusreturnarray.
Merge: menggabungkan dua daftar terurut
Karena dua daftarnya sudah urut, angka terkecil yang tersisa selalu ada di paling depan salah satunya. Jadi angka pertama hasil gabungan cukup dicari di antara 2 angka, bukan 7. Itu jawaban tebakannya. i menunjuk angka terdepan left, j menunjuk angka terdepan right:
| Bandingkan | Ambil | result |
|---|---|---|
| 27 dengan 3 | 3 | [3] |
| 27 dengan 9 | 9 | [3, 9] |
| 27 dengan 10 | 10 | [3, 9, 10] |
| 27 dengan 82 | 27 | [3, 9, 10, 27] |
| 38 dengan 82 | 38 | [3, 9, 10, 27, 38] |
| 43 dengan 82 | 43 | [3, 9, 10, 27, 38, 43] |
Sekarang left habis, jadi loop while berhenti. Sisa right, yaitu [82], tinggal ditempel di belakang.
left[i++]artinya: ambilleft[i], lalu tambahisatu, supaya angka depan berikutnya yang dibandingkan.[...result, ...left.slice(i), ...right.slice(j)]menempel sisa yang belum terambil....menuang isi sebuah array ke array baru.<=mengambil dari kiri kalau nilainya sama, jadi data yang sama tetap di urutan aslinya. Sort yang menjaga urutan itu disebut stabil.
Kenapa selalu O(n log n)
Big-O bilang seberapa cepat kerja algoritma bertambah saat datanya bertambah. O(n) artinya datanya dua kali lipat, waktunya kira-kira dua kali lipat.
- Membelah dua terus butuh sekitar log n level: 8 angka 3 level, 1.000 angka sekitar 10 level.
- Di tiap level, merge menyentuh semua n angka satu kali, jadi kerjanya O(n) per level.
- Totalnya n kali log n, O(n log n): 1.000 angka sekitar 10.000 langkah. Bubble sort butuh sekitar 500.000 perbandingan.
Ini berlaku untuk data apa pun, acak, terbalik, atau hampir urut, karena merge sort selalu membelah di tengah. Harganya memori: slice dan result bikin array baru, jadi butuh memori tambahan sekitar n angka, O(n).
⚠️ Jebakan yang sering ketemu
- Sisa yang lupa ditempel. Loop
whileberhenti begitu salah satu daftar habis. Kalau sisa daftar lainnya gak ditempel, angka-angka terbesar hilang dari hasil. - Lupa
return. Tanpareturn, function mengembalikanundefined, dan.join(',')di belakangnya error. - Base case hilang. Tanpa
if (arr.length <= 1) return arr;, rekursinya gak pernah berhenti dan berakhir dengan errorMaximum call stack size exceeded.
TL;DR: Merge sort membelah array jadi dua sampai tiap bagian tinggal 1 angka (base case), lalu menggabungkan pasangan bagian yang sudah terurut. Merge membandingkan angka terdepan dua daftar, mengambil yang lebih kecil, lalu menempel sisanya. Ada log n level dan tiap level kerjanya n, jadi selalu O(n log n), apa pun datanya. Merge sort stabil, tapi butuh memori tambahan O(n).
