• JavaScript Solution
• C Solution

  紧接着上一篇的快速排序，本文主要来讲一下归并排序。快速排序，归并排序，以及堆排序，也就是我们排序里可能会经常用到的三种了。学会它们，也可以会不少的题目。先上Js和C的递归写法吧。

下面先上归并排序的排序过程：

归并排序过程

JavaScript Solution

function MergeSort(data) {
  if (data.length === 1) return data;
  else {
    let middle = parseInt(data.length / 2);
    let left = data.slice(0, middle);
    let right = data.slice(middle);
    return Merge(MergeSort(left), MergeSort(right));
  }
}

function Merge(left, right) {
  let arr = [];
  let l = 0,
    r = 0;
  while (l < left.length && r < right.length) {
    if (left[l] < right[r]) arr.push(left[l++]);
    else arr.push(right[r++]);
  }

  while (l < left.length) arr.push(left[l++]);

  while (r < right.length) arr.push(right[r++]);

  return arr;
}

unsort = [1, 0, 2, 9, 3, 8, 4, 7, 5, 6];
console.log(MergeSort(unsort));

---

C Solution

void merge(int arr[], int low, int mid, int high){
    int i = low, j = mid + 1;    //左右指针
    int k = 0;  //工作指针
	int* temp = (int*) malloc (sizeof(int) * (high-low+1));  //暂存数组
    for(;i<=mid && j <= high; k++){  // 比较两个指针所指向的元素
        if(arr[i]<=arr[j])
            temp[k] = arr[i++];
        else
        	temp[k] = arr[j++];
     }


    while(i <= mid) temp[k++] = arr[i++]
    while(j <= mid) temp[k++] = arr[j++]

    for(k=0 ; k<high-low+1; k++)
        arr[low+k] = temp[k];

    return;
}

void MergeSort(int arr[], int left, int right){
    if( left < right ){
        int mid = left + (right - left) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid+1, right);
        Merge(arr, left, mid, right);
    }
    return;
}