blob: e2cfe0186aed19b4f35861719a04ba5ea4e0451a (
plain)
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
|
package sort
import (
"github.com/snonux/algorithms/ds"
)
func Merge(a ds.ArrayList) ds.ArrayList {
aux := make(ds.ArrayList, len(a))
mergeSort(a, aux)
return a
}
func mergeSort(a, aux ds.ArrayList) {
l := len(a)
if l <= 10 {
Insertion(a)
return
}
mi := l / 2
mergeSort(a[0:mi], aux[0:mi])
mergeSort(a[mi:], aux[mi:])
merge(a, aux, 0, mi, l-1)
}
func merge(a, aux ds.ArrayList, lo, mi, hi int) {
for i := lo; i <= hi; i++ {
aux[i] = a[i]
}
i := lo
j := mi
for k := lo; k <= hi; k++ {
switch {
case i >= mi:
a[k] = aux[j]
j++
case j > hi:
a[k] = aux[i]
i++
case aux[i] > aux[j]:
a[k] = aux[j]
j++
default:
a[k] = aux[i]
i++
}
}
}
|
