merge_sort.go

//usr/bin/env go run $0 $@ ; exit

package main

import (
    "fmt"
    "math/rand"
)

func merge_sort(data []int, low int, up int) []int {
    // sanity check
    if up - low < 1 {
        panic("merge_sort: Invalid argument")
    }

    if up - low == 1 {
        return data[low:up]
    }

    run1 := merge_sort(data, low, low + (up - low) / 2)
    run2 := merge_sort(data, low + (up - low) / 2, up)
    merged_run := make([]int, up - low)

    i, i1, i2 := 0, 0, 0
    for {
        if i2 == len(run2) || (i1 < len(run1) && run1[i1] < run2[i2]) {
            merged_run[i] = run1[i1]
            i++
            i1++
        } else {
            merged_run[i] = run2[i2]
            i++
            i2++
        }

        if i1 == len(run1) && i2 == len(run2) {
            break
        }
    }

    return merged_run
}

func main() {
    rand.Seed(0)

    // generate random number array
    var data = make([]int, 20)
    for i, _ := range data {
        data[i] = rand.Intn(100)
    }

    fmt.Println(data)

    // sort by Merge Sort
    data = merge_sort(data, 0, len(data))

    // check whether the array is sorted.
    for i := 0; i < len(data) - 1; i++ {
        if data[i] > data[i + 1] {
            panic(i)
        }
    }

    fmt.Println(data)
}