多语言实现归并排序算法

概述

归并算法采用分治法:
1: 把长度为 n 的 array 分成两半。
3: 把左半边 array 及右半边 array 分别以 Merge Sort 进行 sorting。 (recursive)
3: merge 左半边及右半边 sorted array。

PHP 实现（递归方法）

function mergeSort(array $array):array
{
    $count = count($array);
    if($count < 2){
        return $array;
    }

    $left = $right = [];
    $middle = round($count / 2);

    $left = array_slice($array, 0, $middle);
    $right = array_slice($array, $middle);

    $leftArray = mergeSort($left);
    $rightArray = mergeSort($right);

    return merge($leftArray, $rightArray);
}

function merge(array $leftArray, array $rightArray):array
{
    $tempArray = [];
    while (count($left) > 0 && count($right) > 0) {
        if($left[0] < $right[0]){
            $tempArray[] = array_shift($left);
        } else {
            $tempArray[] = array_shift($right);
        }
    }

    return array_merge($tempArray, $left, $right);
}


var_export(mergeSort([12, 34, 3, 2, 67, 21, 1, 56]));

JavaScript 实现（递归法）

function memgeSort(array){
  var left = [], right = [], leftArray = [], rightArray = [];
  var len = array.length
  if(len < 2){
     return array
  }
  
  var middle = parseInt(len / 2)
  left = array.slice(0, middle)
  right = array.slice(middle)

  leftArray = memgeSort(left)
  rightArray = memgeSort(right)
  
  return sort(left, right)
}

function sort(left, right){
  var res = [];
 
  while(left.length > 0 && right.length > 0 ){
        if(left[0] < right[0]){
          res.push(left.shift())
        } else {
          res.push(right.shift())
        }
  }
  
  return res.concat(left, right)
}