Go排序算法——插入排序与归并排序

package main

import (
    "fmt"
    "math"
    "math/rand"
    "time"
)

func insertionSort(array []int) {
    length := len(array)
    for j := 1; j < length; j++ {
        key := array[j]
        i := j - 1
        for i >= 0 && array[i] > key {
            array[i+1] = array[i]
            i--
        }
        array[i+1] = key
    }
}

func randomArray(length int) (array []int) {
    array = make([]int, length)
    for i := 0; i < length; i++ {
        array[i] = rand.Intn(100000000)
    }
    return array
}

func mergeSort(array []int, p, r int) {
    if p < r {
        q := (p + r) / 2
        mergeSort(array, p, q)
        mergeSort(array, q+1, r)
        merge(array, p, q, r)
    }
}

func merge(array []int, p, q, r int) {
    length1 := q - p + 1
    length2 := r - q
    L, R := make([]int, length1+1), make([]int, length2+1)
    for i := 0; i < length1; i++ {
        L[i] = array[p+i]
    }
    for i := 0; i < length2; i++ {
        R[i] = array[q+1+i]
    }
    L[length1], R[length2] = math.MaxInt64, math.MaxInt64
    i, j := 0, 0
    for k := p; k < r+1; k++ {
        if L[i] <= R[j] {
            array[k] = L[i]
            i++
        } else {
            array[k] = R[j]
            j++
        }
    }
}

func main() {
    for i := 0; i < 5; i++ {
        arr := randomArray(100000)
        start := time.Now()
        mergeSort(arr, 0, 99999)
        duration := time.Since(start)
        fmt.Println(duration)
    }
}

用归并排序与插入排序分别进行五次数据规模为10万的数组排序，结果如下。

归并排序 插入排序