# 归并排序 ```javascript function mergeSort(arr) { let length = arr.length; if (length === 1) return arr; let mid = Math.floor(length / 2); let right = arr.slice(mid); let left = arr.slice(0, mid); return merge(mergeSort(left), mergeSort(right)) } function merge(left, right) { let innerLeft = 0; let innerRight = 0; let result = []; while (innerLeft < left.length && innerRight < right.length) { if (left[innerLeft] < right[innerRight]) { result.push(left[innerLeft++]) } else { result.push(right[innerRight++]) } } while (innerLeft < left.length) { result.push(left[innerLeft++]) } while (innerRight < right.length) { result.push(right[innerRight++]) } return result; } var a = [1, 3, 2, 5, 0]; console.log(mergeSort(a)); ``` 在牛客网上有个关于归并算法的应用，题目如下 > 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 > 对应的解法在归并算法的改动下为 ~~~ function mergeSort(arr){         if(arr.length <= 1){             return arr;         }         var left_arr = mergeSort(arr.slice(0, arr.length / 2));         var right_arr = mergeSort(arr.slice(arr.length / 2, arr.length));         return mergeList(left_arr, right_arr);     }     function mergeList(left_arr, right_arr){         var left_index = 0;         var right_index = 0;         var sortArray = [];         var rightCount = 0;   //该位置（包括）之前的来自右数组个数和         while(left_index != left_arr.length && right_index != right_arr.length){             if(left_arr[left_index] < right_arr[right_index]){                 sortArray.push(left_arr[left_index++]);                 sum += rightCount;             }else{                 sortArray.push(right_arr[right_index++]);                 rightCount++;             }         }         while(left_index != left_arr.length){             sortArray.push(left_arr[left_index++]);             sum += rightCount;         }         while(right_index != right_arr.length){             sortArray.push(right_arr[right_index++]);             rightCount++;         }         return sortArray;     }     var sum = 0;     mergeSort([1,2,3,4,5,6,7,0]);     console.log(sum); ~~~