Merge Sort memecah array menjadi bagian-bagian kecil, mengurutkan masing-masing, lalu menggabungkan kembali.

Kompleksitas: O(n log n) — selalu, tidak ada worst case yang lebih lambat

Cara kerja (Divide & Conquer):

1. Divide — bagi array jadi 2 bagian
2. Conquer — urutkan masing-masing (rekursif)
3. Merge — gabungkan 2 bagian yang sudah terurut

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  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, 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)];
}

mergeSort([38, 27, 43, 3, 9, 82, 10]);
// 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:  [27,38] [3,43] [9,82] [10]
// Merge:  [3,27,38,43] [9,10,82]
// Merge:  [3,9,10,27,38,43,82]

Kelebihan:

• Konsisten O(n log n) — tidak ada worst case
• Stabil
• Bagus untuk data besar dan linked list

Kekurangan:

• Butuh O(n) memori tambahan untuk merge
• Overhead rekursi untuk data kecil

🎭 Analogi sehari-hari: Cara mengurutkan 2 tumpukan kartu yang sudah sorted jadi 1 sorted. Bandingin kartu paling atas masing-masing, ambil yang lebih kecil, taruh di tumpukan hasil. Ulangi. Cepet karena gak perlu cek seluruh kartu — cuma top tiap stack. Itulah merge step. Cara ke divide-nya: bagi terus jadi 2 sampai 1 kartu (yang pasti sorted), lalu merge balik.

💡 Mengapa O(n log n) dijamin? Setiap level recursion total kerja = O(n) (merge). Level recursion = log n (karena bagi 2 tiap kali). Total: n × log n = O(n log n). Tidak peduli data sudah sorted atau acak — selalu sama.

⚠️ Jebakan umum:

• arr.slice() setiap recursion = O(n) memory copy tiap call. Lebih hemat: pakai index, slice in-place
• Lupa edge case panjang 1 = infinite recursion
• Spread operator [...left, ...right] boros — pakai loop append manual lebih cepat
• Mendingan iterative bottom-up untuk performa real (no recursion overhead)

🎯 Merge Sort cocok untuk:

• Linked List — gak butuh random access, swap pointer cepat
• External sort — data lebih besar dari RAM (sort di disk)
• Stable sort dijamin — Quick Sort tidak stable
• Worst case matters — finansial, real-time

🧪 Tebakan cepat: 1jt elemen. Merge: konsisten ~20jt operasi. Quick worst case (sorted): 500 milyar operasi. Quick rata-rata: ~20jt. Pakai Merge kalau data adversarial atau predictable performance penting.

TL;DR: Merge Sort = divide & conquer, bagi-bagi sampai 1 lalu merge. O(n log n) konsisten, stable, butuh O(n) extra memory. Foundation TimSort dan external sort.