mergesort.go

package main

import (
	"encoding/csv"
	"os"
	"fmt"
	"strconv"
	"strings"
	"time"
)

func mergesort(s []int) {
	l := len(s)
	if l == 1 {
		return
	}

	m := l / 2

	mergesort(s[:m])
	mergesort(s[m:])

	left := make([]int, len(s[:m]))
	right := make([]int, len(s[m:]))
	copy(left, s[:m])
	copy(right, s[m:])

	i, lc, rc := 0, 0, 0

	for ; lc < m && rc < (l - m); i++ {
		if left[lc] <= right[rc] {
			s[i] = left[lc]
			lc++
		} else {
			s[i] = right[rc]
			rc++
		}
	}
	if lc < m {
		copy(s[i:], left[lc:])
	} else if rc < (l - m) {
		copy(s[i:], right[rc:])
	}
}

func main() {
	start := time.Now()
	fmt.Print("Loading data... ")
	f, _ := os.Open("nums.csv")
	r := csv.NewReader(f)
	s_, _ := r.ReadAll()
	s := make([]int, len(s_[0]))
	for i := 0; i < len(s); i++ {
		s[i], _  = strconv.Atoi(strings.TrimSpace(s_[0][i]))
	}
	fmt.Println(time.Since(start))

	start = time.Now()
	fmt.Print("Starting the sort... ")
	mergesort(s)
	fmt.Println(time.Since(start))
}

/*
 * Local variables:
 * compile-command: "go build mergesort.go":
 * End:
 */

mergesort_conc.go

package main

import (
	"encoding/csv"
	"os"
	"fmt"
	"strconv"
	"strings"
	"time"
)

func merge(s []int, m int) {
	l := len(s)
	left := make([]int, len(s[:m]))
	right := make([]int, len(s[m:]))
	copy(left, s[:m])
	copy(right, s[m:])

	i, lc, rc := 0, 0, 0

	for ; lc < m && rc < (l - m); i++ {
		if left[lc] <= right[rc] {
			s[i] = left[lc]
			lc++
		} else {
			s[i] = right[rc]
			rc++
		}
	}
	if lc < m {
		copy(s[i:], left[lc:])
	} else if rc < (l - m) {
		copy(s[i:], right[rc:])
	}
}

func mergesort(s []int) {
	l := len(s)
	if l == 1 {
		return
	}

	m := l / 2

	mergesort(s[:m])
	mergesort(s[m:])

	merge(s, m)
}

func main() {
	start := time.Now()
	fmt.Print("Loading data...")
	f, _ := os.Open("nums.csv")
	r := csv.NewReader(f)
	s_, _ := r.ReadAll()
	s := make([]int, len(s_[0]))
	for i := 0; i < len(s); i++ {
		s[i], _  = strconv.Atoi(strings.TrimSpace(s_[0][i]))
	}
	fmt.Println(time.Since(start))

	start = time.Now()
	fmt.Print("Starting the sort...")
	l := len(s)
	m := l / 4
	done1 := make(chan bool)
	done2 := make(chan bool)
	done3 := make(chan bool)
	done4 := make(chan bool)
	go func(){ mergesort(s[:m]); done1 <- true }()
	go func(){ mergesort(s[m:2*m]); done2 <- true }()
	go func(){ mergesort(s[2*m:3*m]); done3 <- true }()
	go func(){ mergesort(s[3*m:]); done4 <- true }()
	<-done1
	<-done2
	merge(s[:2*m], m)
	<-done3
	<-done4
	merge(s[2*m:], m)

	merge(s, 2*m)

	fmt.Println(time.Since(start))
}

/*
 * Local variables:
 * compile-command: "go build mergesort_conc.go":
 * End:
 */