归并排序

[louzhedong]

算法名称

归并排序

实现思路

• 主要思路是将数组分为左右两部分
• 先让左右两部分先有序
• 随后将两个有序的数组合并成一个数组
• 左边数组有序的过程又是一个将数组分为左右两部分，分别排序然后合并的过程
• 整个过程是一个递归的过程

算法分析

时间复杂度为O(NlogN)，空间复杂度为O(N)

算法实现

/**
 * 归并排序
 * @param {*} array 
 */
function MergeSort(array) {
  var length = array.length;
  var result = _sort(array, 0, length - 1);
}

function _sort(array, left, right) {
  if (left === right) {
    return;
  }
  var length = right - left;
  var middle = Math.floor(length / 2) + left;
  _sort(array, left, middle);
  _sort(array, middle + 1, right);
  _merge(array, left, middle, right);
}

function _merge(array, left, middle, right) {
  var result = [];
  var i = 0;
  var cursor1 = left, cursor2 = middle + 1;

  while (cursor1 <= middle && cursor2 <= right) {
    if (array[cursor1] < array[cursor2]) {
      result.push(array[cursor1]);
      cursor1++;
    } else {
      result.push(array[cursor2]);
      cursor2++;
    }
    i++;
  }

  while (cursor1 <= middle) {
    result[i++] = array[cursor1++];
  }

  while (cursor2 <= right) {
    result[i++] = array[cursor2++];
  }

  for (var i = 0; i < result.length; i++) {
    array[left + i] = result[i];
  }
}