-
Notifications
You must be signed in to change notification settings - Fork 0
/
merge.go
44 lines (40 loc) · 778 Bytes
/
merge.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
package v2
import "github.com/corrots/data-structures/sort/helper"
func MergeSort(nums []int) {
mergeSort(nums, 0, len(nums)-1)
}
func mergeSort(nums []int, l, r int) {
if r-l <= 15 {
helper.InsertionSort(nums, l, r)
return
}
mid := (l + r) / 2
mergeSort(nums, l, mid)
mergeSort(nums, mid+1, r)
if nums[mid] > nums[mid+1] {
merge(nums, l, mid, r)
}
}
func merge(nums []int, l, mid, r int) {
temp := make([]int, (r-l)+1)
//for i := l; i <= r; i++ {
// temp[i-l] = nums[i]
//}
copy(temp, nums[l:r+1])
i, j := l, mid+1
for k := l; k <= r; k++ {
if i > mid {
nums[k] = temp[j-l]
j++
} else if j > r {
nums[k] = temp[i-l]
i++
} else if temp[i-l] < temp[j-l] {
nums[k] = temp[i-l]
i++
} else {
nums[k] = temp[j-l]
j++
}
}
}