-
Notifications
You must be signed in to change notification settings - Fork 0
/
merge_sort.go
62 lines (58 loc) · 1.11 KB
/
merge_sort.go
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
package merge_sort
import (
"fmt"
cre "merge_sort/compare"
ce "merge_sort/error"
"sync"
)
func merge(left, right []cre.Compare) (buffer []cre.Compare) {
var i int
buffer = make([]cre.Compare, len(left) + len(right))
for len(left) > 0 && len(right) > 0 {
if left[0].Compare(right[0]) {
buffer[i] = left[0]
left = left[1:]
i++
continue
}
buffer[i] = right[0]
right = right[1:]
i++
}
for j := 0; j < len(left); j++ {
buffer[i] = left[j]
i++
}
for j := 0; j < len(right); j++ {
buffer[i] = right[j]
i++
}
return
}
func MergeSort(array []cre.Compare) ([]cre.Compare,error) {
sizeArray := len(array)
if array == nil{
return array, ce.NilPointerError("array is nil")
}
if sizeArray <= 1 {
return array, ce.SizeError(fmt.Sprintf("array size %d", sizeArray))
}
wg := sync.WaitGroup{}
middle := sizeArray / 2
var (
left = array[0:middle]
right = array[middle:sizeArray]
)
var ln, rn []cre.Compare
wg.Add(2)
go func() {
defer wg.Done()
ln, _ = MergeSort(left)
}()
go func() {
defer wg.Done()
rn, _ = MergeSort(right)
}()
wg.Wait()
return merge(ln, rn), nil
}