Penjelasan merge sort: cara kerja, kode, dan kompleksitas

Ide dasar dengan kata-kata sederhana

List dengan nol atau satu elemen sudah terurut. Untuk list yang lebih panjang:

1. Divide: bagi list menjadi bagian kiri dan bagian kanan.
2. Conquer: urutkan setiap bagian dengan merge sort.
3. Combine: gabungkan dua bagian terurut. Bandingkan elemen pertama dari masing-masing, pindahkan yang lebih kecil ke output, dan ulangi sampai salah satu bagian habis; lalu salin sisa bagian yang lain.

Semua pekerjaan sebenarnya terjadi di langkah merge, dan menggabungkan dua list terurut dengan total panjang n hanya butuh paling banyak n − 1 perbandingan.

Contoh langkah demi langkah

Urutkan [38, 27, 43, 3, 9, 82, 10].

Penggabungan terakhir membandingkan elemen depan: 27 vs 3 mengambil 3, 27 vs 9 mengambil 9, 27 vs 10 mengambil 10, 27 vs 82 mengambil 27, 38 vs 82 mengambil 38, 43 vs 82 mengambil 43, lalu 82 disalin. Enam perbandingan untuk tujuh elemen.

Implementasi Python

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= takes from left on ties: stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])            # one of these is empty
    out.extend(right[j:])
    return out
def merge_sort(items):
    """Return a new sorted list."""
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort([]))                           # []

Versi top-down ini jelas tetapi menyalin slice. Versi bottom-up menghindari rekursi sepenuhnya: gabungkan run berlebar 1, lalu 2, lalu 4, dan seterusnya.

def merge_sort_bottom_up(items):
    a = list(items)
    width = 1
    while width < len(a):
        for lo in range(0, len(a), 2 * width):
            mid, hi = lo + width, lo + 2 * width
            a[lo:hi] = merge(a[lo:mid], a[mid:hi])
        width *= 2
    return a

Versi bottom-up memakai ulang merge dari atas. Pustaka standar juga punya heapq.merge, yang menggabungkan sejumlah iterable terurut secara lazy.

Kompleksitas waktu dan ruang

Rekurensinya adalah T(n) = 2T(n/2) + O(n). Setiap tingkat pada pohon rekursi mengerjakan O(n) secara total dan ada sekitar log₂ n tingkat, sehingga totalnya O(n log n). Untuk sejuta item itu sekitar 20 tingkat.

Perbandingan merge sort dengan sort lain

Merge sort stabil karena merge mengambil dari bagian kiri ketika dua elemen sama, sehingga elemen yang sama mempertahankan urutannya. Dibandingkan quicksort, merge sort punya kasus terburuk O(n log n) yang terjamin tetapi butuh memori tambahan O(n) dan biasanya lebih banyak perpindahan data pada array. Dibandingkan heapsort, merge sort stabil dan mengakses memori secara berurutan, yang bersahabat dengan cache dan disk.

Varian dan kesalahan umum

• Natural merge sort mendeteksi run yang sudah terurut dan menggabungkannya, menghasilkan O(n) pada input terurut. Timsort adalah natural merge sort yang disempurnakan dan memakai binary insertion sort untuk run pendek.
• Beralihlah ke insertion sort untuk sublist kecil (misalnya kurang dari sekitar 10 sampai 30 elemen) untuk memangkas overhead.
• Pada linked list, merge sort tidak butuh buffer tambahan: penggabungan hanya menyambung ulang node, sehingga ini pilihan yang lazim untuk mengurutkan linked list.
• External merge sort mengurutkan potongan yang muat di memori, menuliskannya ke disk, lalu melakukan k-way merge. Database dan alat seperti sort dari GNU memakai ide ini untuk file besar.
• Menghitung inversi: saat merge, setiap kali elemen diambil dari bagian kanan, elemen itu lebih kecil daripada semua elemen yang tersisa di bagian kiri.

Kapan memakai merge sort

Pilih merge sort ketika Anda butuh sort stabil dengan waktu O(n log n) yang terjamin, saat mengurutkan linked list, atau ketika data terlalu besar untuk memori. Di Python, cukup panggil sorted() atau list.sort(): keduanya mengimplementasikan Timsort, yang merupakan varian merge sort, jadi sifat-sifat ini sudah Anda dapatkan. Menulis merge sort sendiri adalah tugas wawancara klasik, sering diperluas menjadi menghitung inversi atau menggabungkan k list terurut.