package Sort

import (
	"fmt"
	"testing"
)

func MergeSort1(array []int, l, r int) {
	process1(array, l, r)
}

func process1(array []int, l, r int) {
	if array == nil || len(array) < 2 {
		return
	}
	if l == r {
		return
	}
	m := l + (r-l)/2
	process1(array, l, m)
	process1(array, m+1, r)

	merge(array, l, m, r)
}

func merge(array []int, l, m, r int) {
	help := make([]int, r-l+1)
	i, j, current := l, m+1, 0
	for i <= m && j <= r {
		if array[i] < array[j] {
			help[current] = array[i]
			i++
		} else {
			help[current] = array[j]
			j++
		}
		current++
	}

	for ; i <= m; i, current = i+1, current+1 {
		help[current] = array[i]
	}

	for ; j <= r; j, current = j+1, current+1 {
		help[current] = array[j]
	}

	for i, v := range help {
		array[l+i] = v
	}
}

// 非递归方法实现
func MergeSort2(arr []int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	N := len(arr)
	// 步长
	mergeSize := 1
	for mergeSize < N { // log N
		L := 0 // 当前左组的，第一个位置
		for  L < N {
			if mergeSize >= N-L {
				break
			}
			M := L + mergeSize - 1
			R := M + min(mergeSize, N-M-1)
			merge(arr, L, M, R)
			L = R + 1
		}
		// 防止溢出
		if mergeSize > N/2 {
			break
		}
		mergeSize <<= 1
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func TestMergeSort(t *testing.T) {
	arr := []int{230, 234, 43, 12, 2, 30, 0, 23, 230, 234, 43, 12, 2, 30, 0, 23}
	MergeSort1(arr, 0, len(arr)-1)
	arr1 := []int{230, 234, 43, 12, 2, 30, 0, 23, 230, 234, 43, 12, 2, 30, 0, 23}
	MergeSort2(arr1)
	fmt.Println(arr1)
	fmt.Println(arr)
}