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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
package main
import (
"fmt"
"reflect"
"testing"
)
func Merge(left []int, right []int) []int {
total := len(left) + len(right)
items := []int{}
for i := 0; i < total; i++ {
if len(left) == 0 || len(right) == 0 {
break
}
if left[0] < right[0] {
items, left = append(items, left[0]), left[1:]
} else {
items, right = append(items, right[0]), right[1:]
}
}
for _, item := range left {
items = append(items, item)
}
for _, item := range right {
items = append(items, item)
}
return items
}
func MergeSort(A []int) []int {
length := len(A)
if length <= 1 {
return A
}
mid := length / 2
left := MergeSort(A[0:mid])
right := MergeSort(A[mid:])
return Merge(left, right)
}
func TestMergeSort(t *testing.T) {
table := []struct {
in []int
out []int
}{
{
in: []int{3},
out: []int{3},
},
{
in: []int{3, 41},
out: []int{3, 41},
},
{
in: []int{41, 3},
out: []int{3, 41},
},
{
in: []int{3, 3},
out: []int{3, 3},
},
{
in: []int{3, 41, 9},
out: []int{3, 9, 41},
},
{
in: []int{3, 41, 52, 26, 38, 57, 9, 49},
out: []int{3, 9, 26, 38, 41, 49, 52, 57},
},
}
for _, test := range table {
t.Run(fmt.Sprintf("Sort %v", test.in), func(t *testing.T) {
results := MergeSort(test.in)
if !reflect.DeepEqual(results, test.out) {
t.Errorf("Expected: %v, Got: %v", test.out, test.in)
}
})
}
}
|
