/**
 * 歸并排序 ，采用分而治之(divide - conquer)的步驟
 * 1. 分解（Divide），把待排序元素的序列分解為兩個(gè)子序列，以中間2分, 每個(gè)子序列包括一半成員。
 * 2. 解決（Conquer），對(duì)每個(gè)子序列分別調(diào)用歸并操作, 進(jìn)行遞歸或非遞歸循環(huán)操作，完成內(nèi)部排序。
 * 3. 合并（Combine），合并兩個(gè)排好序的子序列，生成排序結(jié)果。 歸并排序的最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度均為O(nlogn)
 */
(function () {
  // 將兩個(gè)有序數(shù)組合并為一個(gè)新的有序數(shù)組
  function merge (arr, left, mid, right) {
    // 先建立一個(gè)長(zhǎng)度等于原數(shù)組的臨時(shí)數(shù)組
    const temp = []
    // 左側(cè)指針
    let i = left
    // 右側(cè)指針
    let j = mid + 1
    // 臨時(shí)數(shù)組指針
    let k = 0
    // 當(dāng)左指針小于中間，且右指針不大于最右側(cè)時(shí)
    while (i <= mid && j <= right) {
      // 如果左側(cè)小于右側(cè)，將數(shù)移到臨時(shí)數(shù)組中左側(cè)
      if (arr[i] <= arr[j]) {
        temp[k++] = arr[i++]
        // 否則移動(dòng)到臨時(shí)數(shù)組右側(cè)
      } else {
        temp[k++] = arr[j++]
      }
    }
    // 如果左邊數(shù)組還有數(shù)據(jù)，就把左側(cè)剩余都放入到原數(shù)組后面
    while (i <= mid) {
      temp[k++] = arr[i++]
    }
    // 如果右側(cè)數(shù)組還有數(shù)據(jù)，把剩下的數(shù)據(jù)放入到原數(shù)組后面
    while (j <= right) {
      temp[k++] = arr[j++]
    }
    // 將排序后的元素全部移動(dòng)到原數(shù)組中
    let x = 0
    while (left <= right) {
      arr[left++] = temp[x++]
    }
    console.log('arr:', arr)
  }
  function mergeSort (arr, left, right) {
    // 得到中間值
    const mid = Math.floor((left + right) / 2)
    // 如果左側(cè)小于右側(cè)則執(zhí)行合并排序
    if (left < right) {
      // 遞歸合并左側(cè)
      mergeSort(arr, left, mid)
      // 遞歸合并右側(cè)
      mergeSort(arr, mid + 1, right)
      // 合并左右結(jié)果
      merge(arr, left, mid, right)
    }
    return arr
  }
  // test
  const arr = [7, 11, 9, 10, 12, 13, 8, -2, 0, 8]
  console.time('sort')
  console.log('origin:', arr)
  console.log('\r\nsorted:', mergeSort(arr, 0, arr.length - 1))
  console.timeEnd('sort')
})();

(function () {
  function mergeSort (arr) {
    const len = arr.length
    if (len < 2) {
      return arr
    }
    // 取得當(dāng)前數(shù)組的中間位置
    const mid = Math.floor(len / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid)
    console.log('mergeSort arr:', arr, left, right)
    // 遞歸調(diào)用，不斷重復(fù)直到當(dāng)前數(shù)組拆分剩1項(xiàng)
    return merge(mergeSort(left), mergeSort(right))
  }
  // 將兩個(gè)有序數(shù)組進(jìn)行合并為一個(gè)新的有序數(shù)組
  function merge (left, right) {
    // 建立一個(gè)空數(shù)組，用來存放排序結(jié)果
    const result = []
    // 左右數(shù)組的長(zhǎng)度都不為空時(shí)，則將兩個(gè)數(shù)組的第一個(gè)進(jìn)行比較
    // 如左側(cè)小于右，則移除左側(cè)的內(nèi)容到結(jié)果數(shù)據(jù)，反之移動(dòng)右側(cè)成員
    while (left.length && right.length) {
      if (left[0] <= right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }
    // 最后把剩余的左或者右側(cè)成員全部添加到結(jié)果數(shù)組
    while (left.length) {
      result.push(left.shift())
    }
    while (right.length) {
      result.push(right.shift())
    }
    // 這樣一趟下來后，兩個(gè)數(shù)組就合并為一個(gè)新的排序數(shù)組
    return result
  }
})()