Kenapa Merge Sort O(n log n)?

Saya selalu mengira merge sort itu harusnya O(n²) karena dia memecah array dengan ukuran n menjadi array berukuran 1 sebanyak n kemudian digabung dan disortir dengan jumlah operasi sebanyak n kali di setiap iterasinya.

Wajar dong kalau saya kebingungan darimana O(n log n) didapat?

/** * Split the array into halves until all items completely separated * from one another and then sort and merge them recursively along * the way. * @param {Number[]} [array] array of numbers. * @param {Function} [merge] Function to merge 2 `array`s. * @return {Number[]} Sorted array. */ function mergeSort(array, merge) { if (array.length === 1) { return array; } const middleIndex = Math.floor(array.length / 2); const left = array.slice(0, middleIndex); const right = array.slice(middleIndex); const sortedLeft = mergeSort(left); const sortedRight = mergeSort(right); return merge(sortedLeft, sortedRight); }; /** * Merge two array of numbers O(n). * @param {Number[]} [left] array of numbers. * @param {Number[]} [right] array of numbers. * @return {Number[]} Merged array. */ function merge(left, right) { const mergedArray = new array(left.length + right.length); let mergedArrayIndex = 0; let leftArrayIndex = 0; let rightArrayIndex = 0; while(mergedArrayIndex < mergedArray.length) { if (leftArrayIndex < left.length && rightArrayIndex < right.length) { mergedArray[mergedArrayIndex++] = left[leftArrayIndex] < right[rightArrayIndex] ? ( left[leftArrayIndex++] ) : ( right[rightArrayIndex++] ); } else if (leftArrayIndex < left.length) { mergedArray[mergedArrayIndex++] = left[leftArrayIndex++]; } else if (rightArrayIndex < right.length) { mergedArray[mergedArrayIndex++] = right[rightArrayIndex++]; } } return newArray; }

Ternyata saya salah kira. Asumsi membunuhku. Untuk mempermudah memahami konsep, mari kita gunakan array berisi 4 huruf kapital sebagai berikut:

['A', 'Z', 'Y', 'B']

Berikut ilustrasinya:

Bayangkan sedang bermain congklak.

Langkah 1:
Pecah ['A', 'Z', 'Y', 'B'] menjadi ['A', 'Z'] dan ['Y', 'B']. Dihitung 1 langkah.

Langkah 2:
Pecah bagian kiri ['A', 'Z'] menjadi ['A'] dan ['Z']. Dihitung 1 langkah.

Langkah 3:
Gabung dan sortir ['A'] dan ['Z'] menjadi ['A', 'Z']. Ada 2 langkah. Bayangkan permainan congklak.

Langkah 4:
Pecah bagian kanan ['Y', 'B'] menjadi ['Y'] dan ['B']. Dihitung 1 langkah.

Langkah 5:
Gabung dan sortir ['Y'] dan ['B'] menjadi ['B', 'Y]. Ada 2 langkah. Bayangkan permainan congklak.

Langkah 6:
Gabung dan sortir ['A', 'Z'] dan ['B', 'Y'] menjadi ['A', 'B', 'Y', 'Z']. Ada 4 langkah. Bayangkan permainan congklak.

Berdasarkan perhitungan manual, dibutuhkan 11 langkah.

Kalau dikira-kira rumusnya jadi begini c × n × ²log n dan c sebuah konstanta. Gampangnya begini saja, 1.375 × 4 × ²log 4 = 11.

Jika ukuran array sangat besar dan c kita hiraukan, maka kita simpulkan O(n log n).

Kompleksitas merge sort O(n²) jika dan hanya jika jumlah operasi minimal 16 langkah untuk array berukuran 4. Yang kita dapatkan adalah 11 langkah yang berarti benar bahwa kompleksitas merge sort adalah O(n log n).

Paham? Jangan khawatir nanti juga paham sendiri. Ini mirip permainan congklak.

Congklak bro
Divide and conquer!
loading