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?

/**
 * Merge two sorted arrays into one.
 * 
 * Assume the two arrays passed down are sorted. We call it
 * `left` and `right`. Create a new array called `merged`
 * the size of those two combined. Let two variables called
 * `leftIndex` and `rightIndex` track the last position of
 * their corresponding arrays. Iterate through the new array.
 * While in the loop, if the `left` item is bigger than the
 * one in the `right`, insert the `right` item, otherwise
 * insert the `left` item. Go on until one of those two
 * arrays run out of their items. To accomodate the leftover,
 * we just insert all items from whichever array (`left` or
 * `right`) that still got items left because it's sorted. 
 * @param {Number[]} left  - Sorted array
 * @param {Number[]} right - Sorted array
 * @returns {Number[]}
 */
function mergeTwoSortedArrays(left, right) {
  const merged = new Array(
    left.length + right.length
  );

  let leftIndex = 0; // Track the last position of `left`.
  let rightIndex = 0; // Track the last position of `right`.

  for (let index = 0; index < merged.length; index++) {
    if (rightIndex < left.length && leftIndex < left.length) {
      merged[index] = (
        left[leftIndex] > right[rightIndex]
      ) ? (
        right[rightIndex++]
      ) : (
        left[leftIndex++]
      );
    } else if (rightIndex < right.length) {
      // Accomodate the leftover from `right`.
      merged[index] = right[rightIndex++];
    } else if (leftIndex < left.length) {
      // Accomodate the leftover from `left`.
      merged[index] = left[leftIndex++];
    }
  }

  return merged;
}

/**
 * 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.
 * @return {Number[]} Sorted array.
 */
function mergeSort(array) {
  if (array.length === 1) {
    return array;
  }

  const middleIndex = Math.floor(array.length / 2);
  const leftArray = array.slice(0, middleIndex);
  const rightArray = array.slice(middleIndex);

  const sortedLeftArray = mergeSort(leftArray);
  const sortedRightArray = mergeSort(rightArray);

  return mergeTwoSortedArrays(sortedLeftArray, sortedRightArray);
}

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:

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.