algorithm/basic/0004.归并排序/main.go at master · tylitianrui/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package main

import "fmt"

// func merge(left, rigth []int) []int {
// 	i, j := 0, 0
// 	var res = make([]int, 0)
// 	for {

// 		if i == len(left) {
// 			res = append(res, rigth[j:]...)
// 			return res
// 		}
// 		if j == len(rigth) {
// 			res = append(res, left[i:]...)
// 			return res
// 		}

// 		if left[i] <= rigth[j] {
// 			res = append(res, left[i])
// 			i++
// 			continue
// 		}
// 		if left[i] > rigth[j] {
// 			res = append(res, rigth[j])
// 			j++
// 			continue
// 		}

// 	}

// }

func merge(left, right []int) []int {
	l, r := 0, 0
	result := make([]int, 0)
	for l < len(left) && r < len(right) {
		if left[l] <= right[r] {
			result = append(result, left[l])
			l++
		} else {
			result = append(result, right[r])
			r++
		}
	}
	result = append(result, left[l:]...)
	result = append(result, right[r:]...)
	return result
}

func mersort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	l := mersort(arr[:len(arr)/2])
	r := mersort(arr[len(arr)/2:])
	return merge(l, r)

}

func main() {
	l := []int{3, 1, 12, 3, 54, 6, 2, 9, 45, 4, 56}
	r := []int{3}
	fmt.Println(merge(l, r))
	fmt.Println(mersort(l))

}