分治思想--利用归并排序求数组的逆序对

[JesseZhao1990]

var arr = [1,3,20,5,2,9,6,4,80,9,4,6];

function mergeSort(arr){
  let count = 0;

  function _mergeSort(arr, start, end){
    if(start>=end){
      return;
    }
    var middle = Math.floor((start+end)/2);
    _mergeSort(arr, start, middle);
    _mergeSort(arr, middle+1, end);
    merge(arr, start, middle, end);
  }

  function merge(arr, start, middle, end){
     // 开辟临时空间，将start到end的子数组复制到此空间
     const tempArr = arr.slice(start,end+1)
     let index1 = start;
     let index2 = middle+1;

     for(var k=start; k<end; k++){
       if(index1 > middle){
         arr[k] = tempArr[index2- start];
         index2++;
       }else if(index2> end){
         arr[k] = tempArr[index1- start];
         index1++;
       }else if(tempArr[index1-start]< tempArr[index2- start]){
         arr[k] = tempArr[index1-start];
         index1++;
       }else{
        arr[k] = tempArr[index2-start];
        index2++
        count += middle - index1+1;
       }
     }
  }

  _mergeSort(arr, 0, arr.length-1);
  
  return count;
}

mergeSort(arr);