归并排序

归并排序（Merge Sort）是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

package program

import (
    "fmt"
    "testing"
)

var aux []int

func TestMergeSort(t *testing.T) {
    a := []int{2, 2, 3, 2, 5, 1, 6, 7, 9, 21, 44, 77, 21}
    aux = make([]int, len(a))
    sort2(a, 0, len(a)-1)
    t.Log(a)
}

func sort2(a []int, lo, hi int) {
    if hi <= lo {
        return
    }
    mid := lo + (hi-lo)/2
    sort2(a, lo, mid)
    sort2(a, mid+1, hi)
    merge(a, lo, mid, hi)
}

func merge(a []int, low, mid, hi int) {
    i := low
    j := mid + 1
    for k := low; k <= hi; k++ {
        aux[k] = a[k]
    }
    for k := low; k <= hi; k++ {
        if j > hi {
            fmt.Println("i", i)
            a[k] = aux[i]
            i++
        } else if i > mid {
            a[k] = aux[j]
            j++
        } else if aux[i] < aux[j] {
            a[k] = aux[i]
            i++
        } else {
            a[k] = aux[j]
            j++
        }
    }
}