-
Notifications
You must be signed in to change notification settings - Fork 1
/
mergeSort.go
50 lines (44 loc) · 1.24 KB
/
mergeSort.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
package mergeSort
// MergeSort sorts the given slice of integers using the merge sort algorithm.
// The algorithm is stable.
// The algorithm runs in O(n log n) time.
// The algorithm does not require additional memory.
func MergeSort(slice []int) []int {
// Base case.
if len(slice) <= 1 {
return slice
}
// Recursive case. First, divide the list into equal-sized sub lists
// consisting of the first half and second half of the list.
// This assumes lists start at index 0.
var mid int
var left []int
var right []int
// If the list is odd, the middle element is the median.
if len(slice)%2 != 0 {
mid = len(slice) / 2
left = slice[:mid+1]
right = slice[mid+1:]
} else {
mid = len(slice) / 2
left = slice[:mid]
right = slice[mid:]
}
//Recursively sort the sub lists.
left = MergeSort(left)
right = MergeSort(right)
// Merge the two sorted sub lists.
// Merge the two sorted lists into a single sorted list.
var result []int
for len(left) > 0 && len(right) > 0 {
if left[0] < right[0] {
result = append(result, left[0])
left = left[1:]
} else {
result = append(result, right[0])
right = right[1:]
}
}
// Append and return the remaining elements of the list.
return append(append(result, left...), right...)
}