摘要：穩(wěn)定排序穩(wěn)定排序是指，如果原數(shù)組中有多個(gè)元素是相等的，那么這些元素在排序后數(shù)組的相對(duì)順序應(yīng)該保持不變。實(shí)現(xiàn)歸并排序穩(wěn)定排序。的參數(shù)必須為數(shù)組排序范圍順序已經(jīng)正確歸并排序穩(wěn)定排序。

穩(wěn)定排序是指，如果原數(shù)組中有多個(gè)元素是“相等的”，那么這些元素在排序后數(shù)組的相對(duì)順序應(yīng)該保持不變。
比如：我們對(duì){name:string, age:number}[]數(shù)組用age進(jìn)行排序，有很多人是25歲，那么在排序后的數(shù)組中，這些25歲的人應(yīng)該按照它們【在原數(shù)組中出現(xiàn)的順序】來(lái)排列。

原生的sort是不一定是穩(wěn)定的，因?yàn)椴煌囊鎸?shí)現(xiàn)不同，比如V8的sort就用到快排，快排不是穩(wěn)定的排序。

為什么需要穩(wěn)定的排序？其中一種情況是：原列表已經(jīng)在某個(gè)字段上排好序，然而要排序的字段上可能有很多項(xiàng)是“相等”的。
比如有一個(gè){name:string, age:number}[]數(shù)組，它【已經(jīng)在name上按照字母順序排好序】了，現(xiàn)在希望按照age來(lái)排序。假設(shè)有很多人的age是25，如果排序是穩(wěn)定的話，就能保證這些25歲的人【在輸出列表中是按照字母順序排列的】，這樣的話輸出的列表會(huì)好看很多。

/**
 * @description 歸并排序（穩(wěn)定排序）。
 * 此方法會(huì)改變?cè)瓟?shù)組，如果不想破壞原數(shù)組，調(diào)用者自己創(chuàng)建數(shù)組副本作為參數(shù)。
 */
function mergeSort(arr: T[], compare: (a: T, b: T) => -1 | 0 | 1): T[] {
  if (!Array.isArray(arr)) {
    throw new Error("mergeSort的參數(shù)必須為數(shù)組");
  }
  _ms(arr, compare, 0, arr.length);
  return arr;
}

/**
 * @description 排序范圍：[begin, end)
 */
function _ms(arr: T[], compare: (a: T, b: T) => -1 | 0 | 1, begin: number, end: number): void {
  const size = end - begin;
  if (size <= 1) { return; }
  // tslint:disable-next-line: no-bitwise
  const middle = (end + begin) >> 1;
  _ms(arr, compare, begin, middle);
  _ms(arr, compare, middle, end);
  if (compare(arr[middle - 1], arr[middle]) <= 0) { return; } // 順序已經(jīng)正確
  const merged = [];
  let leftIndex = begin, rightIndex = middle;
  while (merged.length < size) {
    if (leftIndex === middle) {
      merged.push(arr[rightIndex++]);
    } else if (rightIndex === end) {
      merged.push(arr[leftIndex++]);
    } else {
      const c = compare(arr[leftIndex], arr[rightIndex]);
      if (c <= 0) {
        merged.push(arr[leftIndex++]);
      } else {
        merged.push(arr[rightIndex++]);
      }
    }
  }
  arr.splice(begin, size, ...merged);
}

/**
 * @description 歸并排序（穩(wěn)定排序）。
 * 此方法會(huì)改變?cè)瓟?shù)組，如果不想破壞原數(shù)組，調(diào)用者自己創(chuàng)建數(shù)組副本作為參數(shù)。
 */
function mergeSort(arr, compare) {
    if (!Array.isArray(arr)) {
        throw new Error("mergeSort的參數(shù)必須為數(shù)組");
    }
    _ms(arr, compare, 0, arr.length);
    return arr;
}
/**
 * @description 排序范圍：[begin, end)
 */
function _ms(arr, compare, begin, end) {
    var size = end - begin;
    if (size <= 1) {
        return;
    }
    // tslint:disable-next-line: no-bitwise
    var middle = (end + begin) >> 1;
    _ms(arr, compare, begin, middle);
    _ms(arr, compare, middle, end);
    if (compare(arr[middle - 1], arr[middle]) <= 0) { return; } // 順序已經(jīng)正確
    var merged = [];
    var leftIndex = begin, rightIndex = middle;
    while (merged.length < size) {
        if (leftIndex === middle) {
            merged.push(arr[rightIndex++]);
        }
        else if (rightIndex === end) {
            merged.push(arr[leftIndex++]);
        }
        else {
            var c = compare(arr[leftIndex], arr[rightIndex]);
            if (c <= 0) {
                merged.push(arr[leftIndex++]);
            }
            else {
                merged.push(arr[rightIndex++]);
            }
        }
    }
    arr.splice(begin, size, ...merged);
}

去leetcode上找一道能用排序的題測(cè)試，比如75. Sort Colors（雖然說(shuō)這道題不用排序效率更高）。