non-recursive merge sort in go

merge_sort.go

package main

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

func sort(data []int, pleft, pleft_end, pright, pright_end int) {

	tmp := make([]int, pright_end-pleft)
	copy(tmp, data[pleft:pright_end])

	i := 0
	i_end := pleft_end - pleft
	j := pright - pleft
	j_end := pright_end - pleft
	x := 0

	for {

		var c int
		if i < i_end && j < j_end {

			if tmp[i] < tmp[j] {
				c = tmp[i]
				i++
			} else {
				c = tmp[j]
				j++
			}
		} else if i < i_end {
			c = tmp[i]
			i++
		} else if j < j_end {
			c = tmp[j]
			j++
		} else {
			break
		}
		data[pleft+x] = c
		x++
	}
}

func merge_sort(data []int) {

	step := 1
	data_length := len(data)
	for {

		if step >= data_length {
			break
		}

		left := 0
		right := left + step

		for {

			left_end := left + step
			if left_end > data_length {
				left_end = data_length
			}
			right_end := right + step
			if right_end > data_length {
				right_end = data_length
			}

			sort(data, left, left_end, right, right_end)

			left = right_end
			right = left + step

			if left == data_length {
				break
			}
		}
		step *= 2
	}
}

func main() {

	size := 1000000
	data := make([]int, size)
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	for i := 0; i < size; i++ {
		data[i] = r.Intn(size*10)
	}
	start := time.Now()
	merge_sort(data)
	elapsed := time.Since(start)
	fmt.Printf("%v\n", data)
	fmt.Printf("Elapsed: %s\n", elapsed)
}