3-2 归并

func sortArray(nums []int) []int {
    mergeNums := make([]int, len(nums))
    mergeSort(nums, mergeNums, 0, len(mergeNums)-1)
    return nums
}

func mergeSort(nums []int, mergeNums []int, l int, r int) {
    if l == r {
        return
    }
    middle := (l + r) / 2
    mergeSort(nums, mergeNums, l, middle)
    mergeSort(nums, mergeNums, middle+1, r)
    merge(nums, mergeNums, l, middle, r)
}

func merge(nums []int, mergeNums []int, l int, middle int, r int) {
    i, j := l, middle+1
    index := l
    for i <= middle && j <= r {
        if nums[i] < nums[j] {
            mergeNums[index] = nums[i]
            i++
        } else if nums[i] >= nums[j] {
            mergeNums[index] = nums[j]
            j++
        }
        index++
    }

    for i <= middle {
        mergeNums[index] = nums[i]
        i++
        index++
    }

    for j <= r {
        mergeNums[index] = nums[j]
        j++
        index++
    }
    for ; l <= r; l++ {
        nums[l] = mergeNums[l]
    }
}

func splitList(head *ListNode) *ListNode {
    fast, slow := head, head
    pre := head
    for fast != nil && fast.Next != nil {
        pre = slow
        fast = fast.Next.Next
        slow = slow.Next
    }
    pre.Next = nil
    return slow
}

func merge(l1, l2 *ListNode) *ListNode {
    head := &ListNode{}
    pre := head
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val{
            pre.Next = l1
            l1 = l1.Next
        }else {
            pre.Next = l2
            l2 = l2.Next
        }
        pre = pre.Next
    }
    if l1 != nil{
        pre.Next = l1
    }else if l2 != nil{
        pre.Next = l2
    }
    return head.Next
}

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    head2 := splitList(head)
    return merge(sortList(head), sortList(head2))
}