Merge Sort: Bagi, Urutkan, Gabungkan
Implementasikan merge sort secara rekursif, telusuri pohon divide-and-conquer, dan jelaskan alasan algoritma ini menjamin O(n log n) dalam semua kasus.
Merge Sort: Bagi, Urutkan, Gabungkan adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Intuisi Bagi dan Taklukkan
Pengurutan gabung adalah algoritme klasik bagi-dan-taklukkan: bagi larik menjadi dua, urutkan setiap bagian secara rekursif, lalu gabungkan kedua bagian yang sudah terurut menjadi satu hasil terurut. Wawasannya adalah bahwa menggabungkan dua larik terurut memerlukan O(n) — jauh lebih murah daripada mengurutkan dari awal. Dekomposisi ini menghasilkan pohon rekursi dengan log n tingkat, yang masing-masing memerlukan kerja penggabungan O(n), sehingga memberikan batas optimal untuk pengurutan berbasis perbandingan, yaitu O(n log n).
# High-level merge sort structure
def merge_sort(arr):
# Base case: 0 or 1 element already sorted
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
# Conquer (merge)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]Penjelasan Langkah Penggabungan
Untuk menggabungkan dua larik terurut, pertahankan dua penunjuk, masing-masing untuk satu bagian. Bandingkan elemen terdepan; salin elemen yang lebih kecil ke keluaran dan majukan penunjuk tersebut. Ketika salah satu bagian habis, salin sisa bagian lainnya secara langsung. Proses ini berjalan dalam waktu O(n) dan menggunakan ruang O(n) untuk larik keluaran. Langkah penggabungan adalah inti algoritmik pengurutan gabung — pahami langkah ini secara mendalam.
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves stability
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]Implementasi Lengkap Pengurutan Gabung
Menggabungkan pembagian dan penggabungan: pemanggilan rekursif membagi dua masalah hingga tersisa elemen tunggal (yang sudah terurut secara langsung), lalu pemanggilan penggabungan menggabungkannya kembali. Setiap tingkat pohon rekursi menggabungkan total n elemen yang sama (yang didistribusikan ke beberapa penggabungan). Kedalaman rekursi adalah log₂(n), sehingga total waktu O(n log n) dan ruang tambahan O(n) untuk larik keluaran penggabungan, ditambah kedalaman tumpukan pemanggilan O(log n).
def merge_sort_full(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_full(arr[:mid])
right = merge_sort_full(arr[mid:])
# Merge the two sorted halves
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: merged.append(left[i]); i += 1
else: merged.append(right[j]); j += 1
merged.extend(left[i:] + right[j:])
return merged
print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]Pohon Rekursi Pengurutan Gabung
Visualisasikan pohon rekursi pengurutan gabung untuk n=8: Tingkat 0 memiliki satu larik berisi 8 elemen; Tingkat 1 memiliki dua larik berisi 4 elemen; Tingkat 2 memiliki empat larik berisi 2 elemen; Tingkat 3 memiliki delapan elemen tunggal (kasus dasar). Saat naik kembali, Tingkat 3→2 menggabungkan total 8 elemen, Tingkat 2→1 menggabungkan total 8 elemen, dan Tingkat 1→0 menggabungkan total 8 elemen. Jadi, 3 tingkat × 8 elemen = 24 operasi ≈ 8 × log₂(8) = 24. Hal ini menegaskan O(n log n).
# Trace the tree depth
level_work = []
def merge_sort_traced(arr, depth=0):
if depth >= len(level_work):
level_work.append(0)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_traced(arr[:mid], depth+1)
right = merge_sort_traced(arr[mid:], depth+1)
level_work[depth] += len(arr) # track merge work
merged = sorted(left + right) # simplified merge
return merged
merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
print(f'Level {d}: {work} elements merged')Pengurutan Gabung di Tempat
Pengurutan gabung rekursif standar mengalokasikan ruang tambahan O(n) untuk keluaran penggabungan. Pengurutan gabung di tempat tersedia, tetapi rumit dan memiliki konstanta yang besar — jarang ditanyakan dalam wawancara. Pertanyaan lanjutan yang umum dalam wawancara adalah: ‘Dapatkah Anda melakukan pengurutan gabung dengan ruang ekstra O(1)?’ Jawaban yang benar: ‘Secara teori, ya, tetapi implementasi praktis mengorbankan ruang O(n) atau menambah kerumitan; Timsort Python menggunakan ruang O(n) untuk penggabungan.’
# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
n = len(arr)
width = 1
while width < n:
for i in range(0, n, 2 * width):
left = arr[i:i+width]
right = arr[i+width:i+2*width]
# Merge and put back
merged = []
a, b = 0, 0
while a < len(left) and b < len(right):
if left[a] <= right[b]: merged.append(left[a]); a+=1
else: merged.append(right[b]); b+=1
merged += left[a:] + right[b:]
arr[i:i+len(merged)] = merged
width *= 2
return arr
print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]Pengurutan Gabung Bersifat Stabil
Pengurutan gabung bersifat stabil: elemen yang sama dari paruh kiri selalu muncul sebelum elemen yang sama dari paruh kanan dalam keluaran yang digabungkan. Hal ini dijamin dengan menggunakan <= (bukan <) saat memilih elemen kiri. Kestabilan penting untuk pengurutan dengan banyak kunci. sorted() bawaan Python dan list.sort() menggunakan Timsort, yang juga stabil dan memiliki O(n log n), sehingga menjadi pilihan aman untuk semua kode produksi.
# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items) # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)Menggabungkan K Larik Terurut
Menggabungkan k larik terurut dengan total n elemen dapat dilakukan dengan berulang kali menggabungkan pasangan (seperti bagan turnamen), dengan waktu O(n log k). Setiap tingkat penggabungan memproses n elemen, dan terdapat log k tingkat. Sebagai alternatif, gunakan heap minimum berukuran k: masukkan elemen terkecil yang tersisa dari setiap larik, keluarkan elemen minimum, lalu masukkan elemen berikutnya dari larik tersebut. Pendekatan heap juga memiliki O(n log k), tetapi lebih hemat memori ketika k sangat besar.
import heapq
def merge_k_sorted(arrays):
result = []
heap = []
# Push first element from each array with array index
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_i, elem_i = heapq.heappop(heap)
result.append(val)
if elem_i + 1 < len(arrays[arr_i]):
next_val = arrays[arr_i][elem_i + 1]
heapq.heappush(heap, (next_val, arr_i, elem_i+1))
return result
arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs)) # [1,2,3,4,5,6,7,8,9]Menghitung Inversi dengan Pengurutan Gabung
Menghitung inversi (pasangan dengan a[i] > a[j] dan i < j) dalam O(n log n) menggunakan pengurutan gabung yang dimodifikasi. Selama langkah penggabungan, ketika sebuah elemen dari sublarik kanan lebih kecil daripada elemen dari sublarik kiri, elemen tersebut membentuk inversi dengan setiap elemen yang tersisa di sublarik kiri. Tambahkan len(left) - i ke hitungan pada saat itu.
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, l_inv = count_inversions(arr[:mid])
right, r_inv = count_inversions(arr[mid:])
merged = []
inversions = l_inv + r_inv
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
inversions += len(left) - i # all remaining left elements > right[j]
merged.extend(left[i:] + right[j:])
return merged, inversions
_, inv = count_inversions([3, 1, 2])
print(inv) # 2: (3,1) and (3,2)Pengurutan Gabung dibandingkan dengan Pengurutan Cepat
Pengurutan gabung menjamin O(n log n) dalam semua kasus, bersifat stabil, dan merupakan pilihan yang lebih baik untuk daftar tertaut serta pengurutan eksternal. Pengurutan cepat memiliki kasus rata-rata O(n log n), tetapi kasus terburuk O(n²), dilakukan di tempat (ruang tumpukan O(log n)), dan sering kali lebih cepat dalam praktik karena efisiensi cache pada larik. sort bawaan Python menggunakan Timsort (varian pengurutan gabung) — selalu menjadi pilihan bawaan yang tepat.
# Head-to-head complexity comparison:
# Algorithm | Best | Avg | Worst | Space | Stable
# Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Insertion sort| O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Merge sort | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No
print('Merge sort: stable, O(n log n) guaranteed, O(n) space')Pengurutan Eksternal: Pengurutan Gabung dalam Skala Besar
Pengurutan gabung adalah algoritme di balik pengurutan eksternal (mengurutkan data yang terlalu besar untuk dimuat ke dalam RAM). Data dibaca dalam beberapa potongan, setiap potongan diurutkan di memori, lalu potongan-potongan tersebut digabungkan dari disk. Langkah penggabungan membaca satu elemen setiap kali dari setiap rangkaian terurut, dengan hanya menyimpan O(k) elemen di memori sekaligus (satu elemen per rangkaian). Inilah alasan pengurutan gabung digunakan dalam basis data, Hadoop MapReduce, dan algoritme pengurutan pita klasik.
# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
chunks = []
for i in range(0, len(data), chunk_size):
chunk = sorted(data[i:i+chunk_size]) # sort in-memory
chunks.append(chunk)
print(f'Created {len(chunks)} sorted chunks')
# Merge all chunks
import heapq
heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
heapq.heapify(heap)
result = []
while heap:
val, ci, ei = heapq.heappop(heap)
result.append(val)
if ei + 1 < len(chunks[ci]):
heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
return result
print(external_sort(list(range(20,0,-1)), 5)[:10])Ringkasan Pengurutan Gabung dan Kiat Wawancara
Dalam wawancara, implementasi pengurutan gabung yang rapi menunjukkan pemahaman tentang rekursi, langkah penggabungan, dan pendekatan bagi-dan-taklukkan. Pertanyaan lanjutan yang umum:
- Mengapa O(n log n), bukan O(n²)? (log n tingkat × n pekerjaan per tingkat)
- Apakah algoritme ini stabil? (Ya, gunakan <= dalam penggabungan)
- Berapa banyak ruang yang digunakan? (Tambahan O(n) + tumpukan O(log n))
- Apakah dapat dilakukan secara iteratif? (Ya, dengan pengurutan gabung dari bawah ke atas)
- Bagaimana cara menggunakannya pada daftar tertaut? (Lebih mudah daripada pada larik — tidak ada biaya potongan O(n); gunakan pendekatan lambat-cepat untuk menemukan titik tengah)
# One-shot merge sort for interview clarity:
def ms(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: res.append(l[i]); i+=1
else: res.append(r[j]); j+=1
return res + l[i:] + r[j:]
print(ms([5,2,4,6,1,3])) # [1,2,3,4,5,6]Uji Cepat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini, Anda mempelajari: pengurutan gabung membagi larik di titik tengah, mengurutkan setiap paruh secara rekursif, dan menggabungkan kedua paruh terurut dalam O(n) — menghasilkan waktu eksekusi total O(n log n) di seluruh log n tingkat rekursi, langkah penggabungan menggunakan <= untuk mengambil elemen kiri saat terjadi seri, sehingga menjamin kestabilan, dan pengurutan gabung merupakan algoritme pilihan untuk daftar tertaut, pengurutan eksternal, dan situasi yang memerlukan kestabilan — sedangkan pengurutan cepat lebih disukai untuk larik dalam memori ketika ruang terbatas. Selanjutnya, kita akan mengimplementasikan pengurutan cepat dan menjelajahi strategi pemilihan poros.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Merge Sort: Bagi, Urutkan, Gabungkan” gratis?
Ya — teks lengkap “Merge Sort: Bagi, Urutkan, Gabungkan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Merge Sort: Bagi, Urutkan, Gabungkan”?
Implementasikan merge sort secara rekursif, telusuri pohon divide-and-conquer, dan jelaskan alasan algoritma ini menjamin O(n log n) dalam semua kasus. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Merge Sort: Bagi, Urutkan, Gabungkan” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Bubble Sort dan Insertion Sort
- Merge Sort: Bagi, Urutkan, Gabungkan
- Quick Sort dan Pemilihan Pivot
- Pengurutan Tanpa Perbandingan dan sort() Python