object MergeSort {
    /**
      * 測試歸并排序
      * @param args
      */
    def main(args: Array[String]): Unit = {
        var arr = Array(-8, 4, 1, 889, 56, -37)
        var tmp = new Array[Int](arr.length)
        mergeSort(arr, 0, arr.length-1, tmp)
        for (elem <- arr) {
            println(elem)
        }
    }

    /**
      *
      * @param arr   待排序的數(shù)組
      * @param left  ：最初的左邊的下標(biāo)：0
      * @param right ：最初的右邊下標(biāo)：length-1
      * @param tmp   ：臨時數(shù)組，事先開辟好的，大小和arr一樣
      */

    def mergeSort(arr: Array[Int], left: Int, right: Int, tmp: Array[Int]): Unit = {
        if (left < right) {
            //只要left<right,就可以繼續(xù)分,直到將所有元素全部打散成單個
            //取數(shù)組中間值下標(biāo)
            val mid = (left + right) / 2
            //對數(shù)組中間元素左側(cè)遞歸切分
            mergeSort(arr, left, mid, tmp)
            //對數(shù)組中間元素右側(cè)遞歸切分
            mergeSort(arr, mid + 1, right, tmp)
            //merge是合并的操作
            merge(arr, left, mid, right, tmp)
        }
    }

    def merge(arr: Array[Int], left: Int, mid: Int, right: Int, tmp: Array[Int]) = {
        var i = left //左邊的開始下標(biāo)
        var j = mid + 1 //右邊的開始下標(biāo)
        var t = 0 //臨時數(shù)組tmp的下標(biāo)
        while (i <= mid && j <= right) {//同時滿足這兩個條件，說明中間元素左右兩側(cè)均還有元素未放到臨時排序數(shù)組中
            if (arr(i) <= arr(j)) {
                //如果當(dāng)前的左邊的有序列表的值小于當(dāng)前的右邊有序列表的值，把小的值拷貝到tmp數(shù)組中，然后下標(biāo)后移1位
                tmp(t) = arr(i)
                i += 1
                t += 1
            } else {
                tmp(t) = arr(j)
                t += 1
                j += 1
            }
        }
        //不滿足第一個while條件說明有一側(cè)數(shù)據(jù)已經(jīng)全部拷貝到tmp數(shù)組中了
        while (i <= mid) {
            //如果左邊的有序列表中還有數(shù)據(jù)，依次拷貝到tmp數(shù)組中
            tmp(t) = arr(i)
            i += 1
            t += 1
        }
        while (j <= right) {
            //如果右邊的有序列表中還有數(shù)據(jù)，依次拷貝到tmp數(shù)組中
            tmp(t) = arr(j)
            j += 1
            t += 1
        }
        //將本次的tmp數(shù)組的數(shù)據(jù)拷貝到原數(shù)組arr中
        t = 0
        //注意這里原數(shù)組下標(biāo)tmpLeft不從0開始，而是從left開始，因為
        var tmpLeft = left
        while (tmpLeft <= right) {
            arr(tmpLeft) = tmp(t)
            tmpLeft += 1
            t += 1
        }
    }
}