Merge Sort
Terakhir diperbarui
Merge sort adalah algoritma divide and conquer. Algoritma ini membagi array menjadi dua secara rekursif sampai setiap bagian hanya berisi satu elemen (yang dengan sendirinya sudah terurut), lalu menggabungkan bagian-bagian itu kembali secara berurutan. Langkah penggabungan menyusuri dua subarray yang terurut dengan dua pointer, dan selalu menyalin elemen terdepan yang lebih kecil sebagai elemen berikutnya. Tekan Putar di atas untuk melihat array dibangun ulang dari satu penggabungan ke penggabungan berikutnya.
Karena selalu membagi dua, merge sort berjalan dalam waktu O(n log n) pada setiap kasus: kasus terburuknya sama baiknya dengan kasus terbaiknya. Harganya adalah ruang tambahan O(n) untuk buffer penggabungan sementara.
Kompleksitas waktu dan ruang
| Kasus | Kompleksitas | Catatan |
|---|---|---|
| Kasus terbaik | O(n log n) | Selalu membagi input menjadi dua |
| Kasus rata-rata | O(n log n) | Urutan acak |
| Kasus terburuk | O(n log n) | Terjamin: tidak ada input yang buruk |
| Ruang | O(n) | Buffer sementara untuk penggabungan |
| Stabil | Ya | Nilai yang sama diambil dari kiri lebih dulu saat penggabungan |
Langkah demi langkah
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Jika rentangnya berisi 0 atau 1 elemen, rentang itu sudah terurut. |
| 2 | Bagi rentang menjadi dua bagian. |
| 3 | Jalankan merge sort secara rekursif pada bagian kiri. |
| 4 | Jalankan merge sort secara rekursif pada bagian kanan. |
| 5 | Gabungkan kedua bagian yang sudah terurut dengan dua pointer. |
Contoh penerapan
Mengurutkan [5, 2, 4, 1]:
| Tahap | Array | Aksi |
|---|---|---|
| Bagi | [5, 2] | [4, 1] | Bagi array menjadi dua bagian |
| Bagi | [5] [2] | [4] [1] | Bagi lagi sampai setiap bagian hanya berisi satu elemen |
| Gabung | [2, 5] | [1, 4] | Gabungkan [5],[2] menjadi [2, 5] dan [4],[1] menjadi [1, 4] |
| Gabung | [1, 2, 4, 5] | Gabungkan [2, 5] dan [1, 4]: ambil 1, lalu 2, lalu 4, lalu 5 |
| Selesai | [1, 2, 4, 5] | Array sudah terurut sepenuhnya |
Kapan memakai merge sort
| Pakai saat | Hindari saat |
|---|---|
Kamu butuh kasus terburuk O(n log n) yang terjamin | Memori terbatas dan ruang tambahan O(n) tidak bisa diterima |
| Stabilitas penting (key yang sama mempertahankan urutannya) | Kamu mengurutkan array kecil, di mana insertion sort lebih cepat |
| Kamu mengurutkan linked list | Pengurutan in-place adalah syarat mutlak |
| Datanya terlalu besar untuk RAM (external sorting) | Lokalitas cache paling menentukan dan putaran in-place milik quicksort lebih unggul |
Kode Merge Sort
Implementasi Merge Sort yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C, Pseudocode. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Merge Sort dalam Python
Python
1def merge_sort(a):2 if len(a) <= 1:3 return a4 mid = len(a) // 25 left = merge_sort(a[:mid])6 right = merge_sort(a[mid:])7 return merge(left, right)8
9
10def merge(left, right):11 out = []12 i = j = 013 while i < len(left) and j < len(right):14 if left[i] <= right[j]:15 out.append(left[i])16 i += 117 else:18 out.append(right[j])19 j += 120 out.extend(left[i:])21 out.extend(right[j:])22 return out23
24
25nums = [38, 27, 43, 3, 9, 82, 10]26print("Before:", nums)27print("After: ", merge_sort(nums))Kode Merge Sort dalam JavaScript
JavaScript
1function mergeSort(arr) {2 if (arr.length <= 1) return arr;3 const mid = Math.floor(arr.length / 2);4 const left = mergeSort(arr.slice(0, mid));5 const right = mergeSort(arr.slice(mid));6 return merge(left, right);7}8
9// Merge two sorted arrays into one sorted array10function merge(left, right) {11 const out = [];12 let i = 0;13 let j = 0;14 while (i < left.length && j < right.length) {15 out.push(left[i] <= right[j] ? left[i++] : right[j++]);16 }17 return out.concat(left.slice(i), right.slice(j));18}19
20const data = [5, 2, 9, 1, 7, 3];21console.log("Before:", data);22console.log("Sorted:", mergeSort(data));Kode Merge Sort dalam Java
Java
1import java.util.Arrays;2
3public class Main {4 static void mergeSort(int[] arr, int left, int right) {5 if (left >= right) return;6 int mid = (left + right) / 2;7 mergeSort(arr, left, mid);8 mergeSort(arr, mid + 1, right);9 merge(arr, left, mid, right);10 }11
12 // Merge two sorted halves into a temp array, then copy back13 static void merge(int[] arr, int left, int mid, int right) {14 int[] tmp = new int[right - left + 1];15 int i = left, j = mid + 1, k = 0;16 while (i <= mid && j <= right) {17 tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];18 }19 while (i <= mid) tmp[k++] = arr[i++];20 while (j <= right) tmp[k++] = arr[j++];21 System.arraycopy(tmp, 0, arr, left, tmp.length);22 }23
24 public static void main(String[] args) {25 int[] arr = {38, 27, 43, 3, 9, 82, 10};26 System.out.println("Before: " + Arrays.toString(arr));27 mergeSort(arr, 0, arr.length - 1);28 System.out.println("After: " + Arrays.toString(arr));29 }30}Kode Merge Sort dalam C++
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void merge(std::vector<int>& a, int lo, int mid, int hi) {10 std::vector<int> tmp;11 tmp.reserve(hi - lo + 1);12 int i = lo, j = mid + 1;13 while (i <= mid && j <= hi) {14 if (a[i] <= a[j]) tmp.push_back(a[i++]);15 else tmp.push_back(a[j++]);16 }17 while (i <= mid) tmp.push_back(a[i++]);18 while (j <= hi) tmp.push_back(a[j++]);19 for (size_t k = 0; k < tmp.size(); ++k) a[lo + k] = tmp[k];20}21
22void mergeSort(std::vector<int>& a, int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main() {31 std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};32 std::cout << "Before: ";33 printVec(data);34 mergeSort(data, 0, static_cast<int>(data.size()) - 1);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Kode Merge Sort dalam C
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void merge(int a[], int lo, int mid, int hi) {10 int* tmp = malloc((hi - lo + 1) * sizeof(int));11 int i = lo, j = mid + 1, k = 0;12 while (i <= mid && j <= hi) {13 if (a[i] <= a[j]) tmp[k++] = a[i++];14 else tmp[k++] = a[j++];15 }16 while (i <= mid) tmp[k++] = a[i++];17 while (j <= hi) tmp[k++] = a[j++];18 for (k = 0; k <= hi - lo; k++) a[lo + k] = tmp[k];19 free(tmp);20}21
22void mergeSort(int a[], int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main(void) {31 int data[] = {38, 27, 43, 3, 9, 82, 10};32 int n = sizeof(data) / sizeof(data[0]);33 printf("Before: ");34 printArr(data, n);35 mergeSort(data, 0, n - 1);36 printf("After: ");37 printArr(data, n);38 return 0;39}Kode Merge Sort dalam Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211DECLARE temp : ARRAY[1:7] OF INTEGER12DECLARE i : INTEGER13
14PROCEDURE merge(lo : INTEGER, mid : INTEGER, hi : INTEGER)15 DECLARE a : INTEGER16 DECLARE b : INTEGER17 DECLARE k : INTEGER18 a ← lo19 b ← mid + 120 k ← lo21 WHILE a <= mid AND b <= hi DO22 IF nums[a] <= nums[b] THEN23 temp[k] ← nums[a]24 a ← a + 125 ELSE26 temp[k] ← nums[b]27 b ← b + 128 ENDIF29 k ← k + 130 ENDWHILE31 WHILE a <= mid DO32 temp[k] ← nums[a]33 a ← a + 134 k ← k + 135 ENDWHILE36 WHILE b <= hi DO37 temp[k] ← nums[b]38 b ← b + 139 k ← k + 140 ENDWHILE41 FOR k ← lo TO hi42 nums[k] ← temp[k]43 NEXT k44ENDPROCEDURE45
46PROCEDURE mergeSort(lo : INTEGER, hi : INTEGER)47 DECLARE mid : INTEGER48 IF lo < hi THEN49 mid ← (lo + hi) DIV 250 // Sort each half, then merge them51 CALL mergeSort(lo, mid)52 CALL mergeSort(mid + 1, hi)53 CALL merge(lo, mid, hi)54 ENDIF55ENDPROCEDURE56
57CALL mergeSort(1, n)58
59FOR i ← 1 TO n60 OUTPUT nums[i]61NEXT iFAQ Merge Sort
Berapa kompleksitas waktu merge sort?
Merge sort bernilai
O(n log n) pada kasus terbaik, rata-rata, dan terburuk, karena selalu membagi array menjadi dua. Algoritma ini memakai ruang tambahan O(n) untuk buffer penggabungan.Apakah merge sort stabil?
Ya, jika langkah penggabungan menangani nilai yang sama dengan mengambil dari bagian kiri lebih dulu. Cara ini menjaga elemen yang sama tetap dalam urutan relatif aslinya, itulah sebabnya merge sort menjadi pilihan umum untuk pengurutan yang stabil.
Mengapa memakai merge sort, bukan quicksort?
Merge sort menjamin
O(n log n) bahkan pada input yang sengaja dibuat buruk dan bersifat stabil, sedangkan quicksort bisa merosot menjadi O(n²). Merge sort juga lebih dipilih untuk linked list dan external sorting. Kekurangannya adalah memori tambahan O(n).Apa perbedaan merge sort dan quicksort?
Keduanya adalah algoritma pengurutan divide and conquer, tetapi quicksort mempartisi di sekitar pivot dan mengurutkan secara in-place dengan ruang stack
O(log n), sedangkan merge sort membagi dua begitu saja dan menggabungkan dengan buffer O(n). Quicksort biasanya lebih cepat dalam praktik berkat lokalitas cache, tetapi merge sort punya kasus terburuk O(n log n) yang terjamin dan bersifat stabil.Kapan sebaiknya memakai merge sort dalam praktik?
Pakai merge sort saat kamu butuh pengurutan stabil dengan batas
O(n log n) yang terjamin, saat mengurutkan linked list (yang tidak butuh akses acak), atau saat melakukan external sorting untuk data yang terlalu besar untuk muat di memori. Hindari merge sort saat memori terbatas, karena algoritma ini butuh ruang tambahan O(n).Apakah merge sort mengurutkan secara in-place?
Tidak. Merge sort standar mengalokasikan buffer sementara
O(n) untuk menggabungkan kedua bagian, jadi tidak in-place. Ada varian penggabungan in-place, tetapi rumit dan entah lebih lambat atau kehilangan stabilitas, jadi versi berbasis buffer tetap menjadi pilihan umum.Sumber terkait
Visualisasi lainnya
