**Merge Sort** adalah algoritma pengurutan berbasis *divide-and-conquer* yang efisien dan stabil, cocok untuk daftar besar. Algoritma ini membagi daftar menjadi sub-daftar yang lebih kecil, mengurutkannya, lalu menggabungkannya kembali menjadi daftar yang terurut.

### Cara Kerja Merge Sort
1. **Divide (Pembagian):**
- Daftar dibagi dua secara rekursif hingga masing-masing sub-daftar hanya berisi satu elemen (atau kosong). Satu elemen dianggap sudah terurut.
2. **Conquer (Penaklukan):**
- Sub-daftar yang sudah terurut digabungkan (*merge*) menjadi satu daftar yang lebih besar, dengan memastikan elemen-elemennya tetap terurut.
3. **Merge (Penggabungan):**
- Proses penggabungan membandingkan elemen dari dua sub-daftar dan menempatkannya dalam urutan yang benar ke dalam daftar baru.

### Langkah-langkah Algoritma
1. Jika daftar memiliki lebih dari satu elemen, bagi daftar menjadi dua bagian (kiri dan kanan).
2. Panggil Merge Sort secara rekursif untuk kedua bagian tersebut.
3. Gabungkan kedua bagian yang sudah terurut dengan membandingkan elemen dari masing-masing bagian dan menyusunnya dalam urutan yang benar.

### Contoh Kode dalam Python
```python
def merge_sort(arr):
if len(arr) <= 1:
return arr

# Bagi daftar menjadi dua bagian
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # Rekursi untuk bagian kiri
right = merge_sort(arr[mid:]) # Rekursi untuk bagian kanan

# Gabungkan dua bagian yang sudah terurut
return merge(left, right)

def merge(left, right):
result = []
i = j = 0

# Bandingkan elemen dari kedua sub-daftar dan gabungkan dalam urutan
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1

# Tambahkan sisa elemen dari sub-daftar kiri (jika ada)
result.extend(left[i:])
# Tambahkan sisa elemen dari sub-daftar kanan (jika ada)
result.extend(right[j:])

return result

# Contoh penggunaan
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print(f"Daftar terurut: {sorted_arr}")
```

**Output Contoh:** `Daftar terurut: [11, 12, 22, 25, 34, 64, 90]`

### Ilustrasi Proses
Misalkan daftar: `[64, 34, 25, 12, 22, 11, 90]`
1. **Pembagian:**
- `[64, 34, 25, 12]` dan `[22, 11, 90]`
- `[64, 34]` dan `[25, 12]`, serta `[22, 11]` dan `[90]`
- Terus hingga setiap sub-daftar memiliki satu elemen: `[64], [34], [25], [12], [22], [11], [90]`
2. **Penggabungan:**
- Gabung `[64], [34]` → `[34, 64]`
- Gabung `[25], [12]` → `[12, 25]`
- Gabung `[34, 64], [12, 25]` → `[12, 25, 34, 64]`
- Gabung `[22], [11]` → `[11, 22]`
- Gabung `[11, 22], [90]` → `[11, 22, 90]`
- Gabung `[12, 25, 34, 64], [11, 22, 90]` → `[11, 12, 22, 25, 34, 64, 90]`

### Karakteristik Merge Sort
- **Kompleksitas Waktu:**
- Terbaik, rata-rata, dan terburuk: **O(n log n)**, karena pembagian daftar (log n) dan penggabungan (n) dilakukan secara konsisten.
- **Kompleksitas Ruang:** O(n), karena membutuhkan ruang tambahan untuk menyimpan sub-daftar sementara saat penggabungan.
- **Stabilitas:** Merge Sort adalah algoritma *stable*, artinya urutan elemen dengan nilai yang sama tetap terjaga.
- **Kegunaan:**
- Efisien untuk daftar besar, terutama pada struktur data seperti linked list.
- Digunakan dalam aplikasi yang membutuhkan pengurutan stabil, seperti pengurutan data eksternal (misalnya, di disk).
- **Kekurangan:**
- Membutuhkan memori tambahan (tidak *in-place*).
- Kurang efisien untuk daftar kecil dibandingkan algoritma seperti Insertion Sort.

### Kapan Menggunakan Merge Sort?
- Ketika stabilitas pengurutan penting.
- Ketika menangani data besar atau data yang tidak muat di memori (external sorting).
- Ketika performa O(n log n) diperlukan tanpa ketergantungan pada distribusi data.

### Perbandingan dengan Algoritma Lain
- **Vs Bubble Sort:** Merge Sort jauh lebih cepat (O(n log n) vs O(n²)), tetapi Bubble Sort lebih sederhana dan hemat memori untuk daftar kecil.
- **Vs Quick Sort:** Kedua memiliki kompleksitas rata-rata O(n log n), tetapi Quick Sort biasanya lebih cepat dalam praktik karena *in-place* dan cache-friendly, meskipun tidak stabil dan bisa O(n²) dalam kasus terburuk.
- **Vs Insertion Sort:** Merge Sort lebih baik untuk daftar besar, sedangkan Insertion Sort lebih efisien untuk daftar kecil atau hampir terurut.

Jika Anda ingin visualisasi langkah demi langkah (misalnya, diagram di canvas), penjelasan lebih mendalam, atau implementasi dalam bahasa lain, beri tahu saya!