blob: 66a7fd61c8454b0a3e69a8a4f017967945effa52 (
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 (
"codeberg.org/snonux/algorithms/ds"
)
func Merge[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
aux := make(ds.ArrayList[V], len(a))
mergeSort(a, aux)
return a
}
func mergeSort[V ds.Number](a, aux ds.ArrayList[V]) {
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[V ds.Number](a, aux ds.ArrayList[V], 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++
}
}
}
|
