归并排序

思路：基本思想是分治策略，先进行划分，再进行合并；

• 先将待排序数组C划分为两个数组A和B，从中间分开；
• 再分别对数组A和B重复上一步，直到每个子数组只剩一个元素时，划分结束；
  如： [12 20 30 21 15 33 26 19 40 25]
  划分为: [12 20 30 21 15] [33 26 19 40 25]
  [12 20] [30 21 15] [33 26] [19 40 25]
  [12] [20] [30] [21 15] [33] [26] [19] [40 25]
  [12] [20] [30] [21] [15] [33] [26] [19] [40] [25]
• 从下往上不断合并数组，每一层合并相邻两个子数组，合并的过程是每次从两个待合并的子数组中选出一个最小的元素放到合并后的数组中，不断重复直到两个子数组中都没有剩余元素为止；
• 依次类推，直到合并到最上层时结束，这时数据排序就完成了；

function merge(left, right) {
      var result = [];
      while (left.length > 0 && right.length > 0) {
        if (left[0] < right[0]) {
          result.push(left.shift());
        } else {
          result.push(right.shift());
        }
      }
      /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */
      return result.concat(left).concat(right);
    }

    function mergeSort(arr) {
      // 将数组进行划分，直到每项只有一个
      if (arr.length == 1) {
        return arr
      };
      var mid = Math.floor(arr.length / 2);
      var left_arr = arr.slice(0, mid),
        right_arr = arr.slice(mid);
      // 数组先划分到不能再划分时，再进行归并排序
      return merge(mergeSort(left_arr), mergeSort(right_arr));
    }

    var arr = [12, 20, 30, 21, 15, 33, 26, 19, 40, 25];
    console.log(mergeSort(arr));