← Kembali ke DSA
🔀
Sorting (Pengurutan)
Merge Sort
Algoritma divide-and-conquer yang membagi array menjadi dua secara rekursif, mengurutkan tiap bagian, lalu menggabungkannya kembali.
Kompleksitas
Waktu (Terbaik)
O(n log n)
Waktu (Rata-rata)
O(n log n)
Waktu (Terburuk)
O(n log n)
Memori
O(n)
Poin Penting
- ›Dijamin O(n log n) di semua kasus, tanpa penurunan performa di kasus terburuk
- ›Stable sort: urutan relatif elemen yang sama tetap terjaga
- ›Butuh ruang tambahan O(n) untuk tahap merge
- ›Pilihan utama untuk mengurutkan linked list (tidak butuh akses acak)
- ›Menjadi dasar external sorting (mengurutkan data yang terlalu besar untuk RAM)
Visualizer Interaktif
Langkah 0 / 0✓ Selesai diurutkan!
LambatCepat
NormalDibandingkanDitukarTerurut
Contoh Kode
Swift
func mergeSort(_ arr: [Int]) -> [Int] {
guard arr.count > 1 else { return arr }
let mid = arr.count / 2
let left = mergeSort(Array(arr[..<mid]))
let right = mergeSort(Array(arr[mid...]))
return merge(left, right)
}
func merge(_ left: [Int], _ right: [Int]) -> [Int] {
var result = [Int]()
var i = 0, j = 0
while i < left.count && j < right.count {
if left[i] <= right[j] { result.append(left[i]); i += 1 }
else { result.append(right[j]); j += 1 }
}
return result + Array(left[i...]) + Array(right[j...])
}
print(mergeSort([38, 27, 43, 3, 9, 82, 10]))
// [3, 9, 10, 27, 38, 43, 82]