-
Notifications
You must be signed in to change notification settings - Fork 0
/
kyu-2751-timeout.go
60 lines (49 loc) · 1.12 KB
/
kyu-2751-timeout.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
package main
import "fmt"
func main() {
var n int
_, _ = fmt.Scan(&n)
list := make([]int, n)
for i := 0; i < n; i++ {
_, _ = fmt.Scan(&list[i])
}
fmt.Println(mergeSort(list))
}
func merge(left []int, right []int) []int {
if len(left) == 0 {
return right
}
if len(right) == 0 {
return left
}
var sortedList []int
currentLeft := 0
currentRight := 0
for currentLeft < len(left) && currentRight < len(right) {
if left[currentLeft] <= right[currentRight] {
sortedList = append(sortedList, left[currentLeft])
currentLeft += 1
if currentLeft == len(left) {
sortedList = append(sortedList, right[currentRight:]...)
return sortedList
}
} else if left[currentLeft] > right[currentRight] {
sortedList = append(sortedList, right[currentRight])
currentRight += 1
if currentRight == len(right) {
sortedList = append(sortedList, left[currentLeft:]...)
return sortedList
}
}
}
return sortedList
}
func mergeSort(data []int) []int {
if len(data) <= 1 {
return data
}
mid := len(data) / 2
left := mergeSort(data[:mid])
right := mergeSort(data[mid:])
return merge(left, right)
}