goroutine sort

goroutine-sort.go

/**
 * a sort demo while learning go goroutine
 * sorting 10 million numbers concurrently
*/

package main

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

type IntS []int

// sort.Interface
func (a IntS) Len() int {
    return len(a)
}

func (a IntS) Swap(i, j int) {
    a[i], a[j] = a[j], a[i]
}

func (a IntS) Less(i, j int) bool {
    return a[i] < a[j]
}
// end sort.Interface

const n = 10000000 // 1e7

func main() {
    var a = IntS{}
    var b = IntS{}
    for i := 0; i < n; i++ {
        var t = rand.Intn(n)
        a = append(a, t)
        b = append(b, t)
    }

    var start1 = time.Now()
    sort.Sort(a)
    fmt.Printf("pkg sort took %.6f seconds\n", time.Since(start1).Seconds())

    var start2 = time.Now()
    superSort(b)
    fmt.Printf("sup sort took %.6f seconds\n", time.Since(start2).Seconds())

}

// super sort with goroutine
func superSort(a IntS) IntS {
    length := len(a)
    if length <= 1 {
        return a
    }

    mid := length / 2
    a1 := a[0: mid]
    a2 := a[mid: length]

    var ch = make(chan int)

    go func() {
        sort.Sort(a1)
        ch <- 1
    }()

    go func() {
        sort.Sort(a2)
        ch <- 1
    }()

    <- ch
    <- ch

    a3 := make([]int, length)
    var i, j, n1, n2 int
    n1 = len(a1)
    n2 = len(a2)
    // merge two sorted list
    for ii := 0; ii < length; ii++ {
        if (i < n1 && j < n2 && a1[i] < a2[j]) || (i < n1 && j == n2) {
            a3[ii] = a1[i]
            i++
            continue
        }

        a3[ii] = a2[j]
        j++
    }

    return a3
}

//[calvin:~/source/test/go]$ go run sort.go
//pkg sort took 3.754109 seconds
//sup sort took 1.980207 seconds