golang 归并排序算法实现

归并排序算法实现

描述
给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。

要求：时间复杂度 O(nlogn) ，空间复杂度 O(n) 示例1

package main
// import "fmt"
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
*/
func merge_sort(arr,temp []int, i,j int ) {
    // n:= len(arr)
    if i>=j { return  }
    mid := (i+j) >>1
    merge_sort(arr,temp,i,mid)
    merge_sort(arr,temp,mid+1,j)
    var x = i
    var y = mid+1
    var k int 
    for x<=mid && y <= j {
        if arr[x] <= arr[y] {
            temp[k] = arr[x]
            x++
        }else {
            temp[k] = arr[y]
            y++
        }
        k++
    }
    for x<=mid {
        temp[k] = arr[x]
        x++
        k++
    }
    for y<=j {
        temp[k] = arr[y]
        y++
        k++
    }
    for k>0 {
        k--
        //fmt.Println(arr[j])
        arr[j] = temp[k]
        j--
        
    }
    
    
    
}



func MySort( arr []int ) []int {
    // write code here
    //n := len(arr)
    var temp = make([]int,len(arr))
    merge_sort(arr,temp,0,len(arr)-1)
    return arr
    
}