-
-
Notifications
You must be signed in to change notification settings - Fork 2.6k
/
timsort.go
71 lines (59 loc) · 1.84 KB
/
timsort.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
61
62
63
64
65
66
67
68
69
70
71
// Implementation of Timsort algorithm
// Reference: https://en.wikipedia.org/wiki/Timsort
package sort
import (
"github.com/TheAlgorithms/Go/constraints"
)
const runSizeThreshold = 8
// Timsort is a simple generic implementation of Timsort algorithm.
func Timsort[T constraints.Ordered](data []T) []T {
runSize := calculateRunSize(len(data))
insertionSortRuns(data, runSize)
mergeRuns(data, runSize)
return data
}
// calculateRunSize returns a run size parameter that is further used
// to slice the data slice.
func calculateRunSize(dataLength int) int {
remainder := 0
for dataLength >= runSizeThreshold {
if dataLength%2 == 1 {
remainder = 1
}
dataLength = dataLength / 2
}
return dataLength + remainder
}
// insertionSortRuns runs insertion sort on all the data runs one by one.
func insertionSortRuns[T constraints.Ordered](data []T, runSize int) {
for lower := 0; lower < len(data); lower += runSize {
upper := lower + runSize
if upper >= len(data) {
upper = len(data)
}
Insertion(data[lower:upper])
}
}
// mergeRuns merge sorts all the data runs into a single sorted data slice.
func mergeRuns[T constraints.Ordered](data []T, runSize int) {
for size := runSize; size < len(data); size *= 2 {
for lowerBound := 0; lowerBound < len(data); lowerBound += size * 2 {
middleBound := lowerBound + size - 1
upperBound := lowerBound + 2*size - 1
if len(data)-1 < upperBound {
upperBound = len(data) - 1
}
mergeRun(data, lowerBound, middleBound, upperBound)
}
}
}
// mergeRun uses merge sort to sort adjacent data runs.
func mergeRun[T constraints.Ordered](data []T, lower, mid, upper int) {
left := data[lower : mid+1]
right := data[mid+1 : upper+1]
merged := merge(left, right)
// rewrite original data slice values with sorted values from merged slice
for i, value := range merged {
data[lower+i] = value
}
}