forked from jainaman224/Algo_Ds_Notes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Merge_Sort.go
42 lines (38 loc) · 710 Bytes
/
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
package main
import "fmt"
func merge(left, right []int) []int {
result := make([]int, len(right)+len(left))
i, j := 0, 0
for i < len(right) && j < len(left) {
if right[i] <= left[j] {
result[i+j] = right[i]
i += 1
} else {
result[i+j] = left[j]
j += 1
}
}
for i < len(right) {
result[i+j] = right[i]
i += 1
}
for j < len(left) {
result[i+j] = left[j]
j += 1
}
return result
}
func MergeSort(array []int) []int {
if len(array) <= 1 {
return array
}
mid := len(array) / 2
right := MergeSort(array[:mid])
left := MergeSort(array[mid:])
return merge(right, left)
}
func main() {
array := []int{2, 4, 3, 1, 6, 8, 4}
result := MergeSort(array)
fmt.Println(result)
}