归并排序

JS 实现归并排序

#include <iostream>
using namespace std;

// 对array数组下标范围在[start， end] 的元素进行排序
void MergeSort(int * array, int start, int end)
 {
  // 递归中止条件
  if(start == end - 1)
    return;
  // 对2个子数组分开排序
  int mid = (start + end) / 2;
  MergeSort(array, start, mid);
  MergeSort(array, mid, end);
  // 分配临时空间存放合并元素
  int * tmp = new int[end - start];
  // 依次取出子数组的元素，进行合并
  int left_idx = start, right_idx = mid, i = 0;
  while (left_idx < mid && right_idx < end)
  {
    if(array[left_idx] < array[right_idx])
      tmp[i++] = array[left_idx++];
    else
      tmp[i++] = array[right_idx++];
  }
  // 如果有子数组元素没有取完，则全部并入临时空间
  while (left_idx < mid)
    tmp[i++] = array[left_idx++];
  while (right_idx < end)
    tmp[i++] = array[right_idx++];
  // 从临时空间复制会返回数组中
  for(int i = 0, idx = start; i < end -start; i++, idx++)
    array[idx] = tmp[i];
  // 释放临时空间
  delete[] tmp;
 }