golang实现归并排序

golang实现归并排序"/>

golang实现归并排序

使用版本: go version go1.12.1

/*
内存中的归并排序
*/
package main

import "fmt"
import "math/rand"

func mergesort(a []int, l int, r int) {
    if l >= r {
        return
    } else {
        mid := (l + r) / 2
        // fmt.Println("call mergesort between", l, " and ", mid)
        mergesort(a, l, mid)
        // fmt.Println("call mergesort between", mid+1, " and ", r)
        mergesort(a, mid+1, r)
        merge(a, l, mid, r)
    }
}

func merge(a []int, l int, mid int, r int) {
    temp := make([]int, 100, 120)
    copy(temp, a)
    t := l
    i, j := l, mid+1
    for {
        if i>mid || j >r {
            break
        }
        if a[i] < a[j] {
            temp[t] = a[i]
            t += 1
            i += 1
        } else {
            temp[t] = a[j]
            t += 1
            j += 1
        }
    }

    for {
        if i > mid {
            break
        }
        temp[t] = a[i]
        t += 1
        i += 1
    }

    for {
        if j > r {
            break
        }
        temp[t] = a[j]
        t += 1
        j += 1
    }

    // fmt.Println("merge result:", temp)
    for i := l; i < r; i++ {
        a[i] = temp[i]
    }

}

func main() {
    var n int
    n = 100
    a := make([]int, 100, 120)
    for i := 0; i < 100; i++ {
        a[i] = rand.Intn(100)
    }
    fmt.Println("start merge sort")
    mergesort(a, 0, n-1)
    fmt.Println("Final result:", a)
}