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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
package qsort
// A type alias is used here so that we can pass values to an avo
// generated assembly routine. At present, we can't figure out how
// to use the uint128 type in function signatures there. A type
// alias allows us to use struct { a, b uint64 } in the signature,
// and implicit conversions only work if you're using a type alias.
type uint128 = struct {
hi uint64
lo uint64
}
type smallsort128 func(data []uint128, base int, swap func(int, int))
type partition128 func(data []uint128, base int, swap func(int, int)) int
func quicksort128(data []uint128, base, cutoff int, smallsort smallsort128, partition partition128, swap func(int, int)) {
for len(data) > 1 {
if len(data) <= cutoff/16 {
smallsort(data, base, swap)
return
}
medianOfThree128(data, base, swap)
p := partition(data, base, swap)
if p < len(data)-p { // recurse on the smaller side
quicksort128(data[:p], base, cutoff, smallsort, partition, swap)
data = data[p+1:]
base = base + p + 1
} else {
quicksort128(data[p+1:], base+p+1, cutoff, smallsort, partition, swap)
data = data[:p]
}
}
}
func insertionsort128(data []uint128, base int, swap func(int, int)) {
for i := 1; i < len(data); i++ {
item := data[i]
for j := i; j > 0 && less128(item, data[j-1]); j-- {
data[j], data[j-1] = data[j-1], data[j]
callswap(base, swap, j, j-1)
}
}
}
func medianOfThree128(data []uint128, base int, swap func(int, int)) {
end := len(data) - 1
mid := len(data) / 2
if less128(data[0], data[mid]) {
data[mid], data[0] = data[0], data[mid]
callswap(base, swap, mid, 0)
}
if less128(data[end], data[0]) {
data[0], data[end] = data[end], data[0]
callswap(base, swap, 0, end)
if less128(data[0], data[mid]) {
data[mid], data[0] = data[0], data[mid]
callswap(base, swap, mid, 0)
}
}
}
func hoarePartition128(data []uint128, base int, swap func(int, int)) int {
i, j := 1, len(data)-1
if len(data) > 0 {
pivot := data[0]
for j < len(data) {
for i < len(data) && less128(data[i], pivot) {
i++
}
for j > 0 && less128(pivot, data[j]) {
j--
}
if i >= j {
break
}
data[i], data[j] = data[j], data[i]
callswap(base, swap, i, j)
i++
j--
}
data[0], data[j] = data[j], data[0]
callswap(base, swap, 0, j)
}
return j
}
func hybridPartition128(data, scratch []uint128) int {
pivot, lo, hi, limit := 0, 1, len(data)-1, len(scratch)
p := distributeForward128(data, scratch, limit, lo, hi)
if hi-p <= limit {
scratch = scratch[limit-hi+p:]
} else {
lo = p + limit
for {
hi = distributeBackward128(data, data[lo+1-limit:], limit, lo, hi) - limit
if hi < lo {
p = hi
break
}
lo = distributeForward128(data, data[hi+1:], limit, lo, hi) + limit
if hi < lo {
p = lo - limit
break
}
}
}
copy(data[p+1:], scratch[:])
data[pivot], data[p] = data[p], data[pivot]
return p
}
func less128(a, b uint128) bool {
return a.hi < b.hi || (a.hi == b.hi && a.lo < b.lo)
}
|
