1 // DO NOT EDIT; AUTO-GENERATED from sort.go using genzfunc.go
3 // Copyright 2016 The Go Authors. All rights reserved.
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file.
9 // Auto-generated variant of sort.go:insertionSort
10 func insertionSort_func(data lessSwap
, a
, b
int) {
11 for i
:= a
+ 1; i
< b
; i
++ {
12 for j
:= i
; j
> a
&& data
.Less(j
, j
-1); j
-- {
18 // Auto-generated variant of sort.go:siftDown
19 func siftDown_func(data lessSwap
, lo
, hi
, first
int) {
26 if child
+1 < hi
&& data
.Less(first
+child
, first
+child
+1) {
29 if !data
.Less(first
+root
, first
+child
) {
32 data
.Swap(first
+root
, first
+child
)
37 // Auto-generated variant of sort.go:heapSort
38 func heapSort_func(data lessSwap
, a
, b
int) {
42 for i
:= (hi
- 1) / 2; i
>= 0; i
-- {
43 siftDown_func(data
, i
, hi
, first
)
45 for i
:= hi
- 1; i
>= 0; i
-- {
46 data
.Swap(first
, first
+i
)
47 siftDown_func(data
, lo
, i
, first
)
51 // Auto-generated variant of sort.go:medianOfThree
52 func medianOfThree_func(data lessSwap
, m1
, m0
, m2
int) {
53 if data
.Less(m1
, m0
) {
56 if data
.Less(m2
, m1
) {
58 if data
.Less(m1
, m0
) {
64 // Auto-generated variant of sort.go:swapRange
65 func swapRange_func(data lessSwap
, a
, b
, n
int) {
66 for i
:= 0; i
< n
; i
++ {
71 // Auto-generated variant of sort.go:doPivot
72 func doPivot_func(data lessSwap
, lo
, hi
int) (midlo
, midhi
int) {
73 m
:= int(uint(lo
+hi
) >> 1)
76 medianOfThree_func(data
, lo
, lo
+s
, lo
+2*s
)
77 medianOfThree_func(data
, m
, m
-s
, m
+s
)
78 medianOfThree_func(data
, hi
-1, hi
-1-s
, hi
-1-2*s
)
80 medianOfThree_func(data
, lo
, m
, hi
-1)
83 for ; a
< c
&& data
.Less(a
, pivot
); a
++ {
87 for ; b
< c
&& !data
.Less(pivot
, b
); b
++ {
89 for ; b
< c
&& data
.Less(pivot
, c
-1); c
-- {
99 if !protect
&& hi
-c
< (hi
-lo
)/4 {
101 if !data
.Less(pivot
, hi
-1) {
106 if !data
.Less(b
-1, pivot
) {
110 if !data
.Less(m
, pivot
) {
119 for ; a
< b
&& !data
.Less(b
-1, pivot
); b
-- {
121 for ; a
< b
&& data
.Less(a
, pivot
); a
++ {
131 data
.Swap(pivot
, b
-1)
135 // Auto-generated variant of sort.go:quickSort
136 func quickSort_func(data lessSwap
, a
, b
, maxDepth
int) {
139 heapSort_func(data
, a
, b
)
143 mlo
, mhi
:= doPivot_func(data
, a
, b
)
145 quickSort_func(data
, a
, mlo
, maxDepth
)
148 quickSort_func(data
, mhi
, b
, maxDepth
)
153 for i
:= a
+ 6; i
< b
; i
++ {
154 if data
.Less(i
, i
-6) {
158 insertionSort_func(data
, a
, b
)
162 // Auto-generated variant of sort.go:stable
163 func stable_func(data lessSwap
, n
int) {
167 insertionSort_func(data
, a
, b
)
171 insertionSort_func(data
, a
, n
)
173 a
, b
= 0, 2*blockSize
175 symMerge_func(data
, a
, a
+blockSize
, b
)
179 if m
:= a
+ blockSize
; m
< n
{
180 symMerge_func(data
, a
, m
, n
)
186 // Auto-generated variant of sort.go:symMerge
187 func symMerge_func(data lessSwap
, a
, m
, b
int) {
192 h
:= int(uint(i
+j
) >> 1)
199 for k
:= a
; k
< i
-1; k
++ {
208 h
:= int(uint(i
+j
) >> 1)
209 if !data
.Less(m
, h
) {
215 for k
:= m
; k
> i
; k
-- {
220 mid
:= int(uint(a
+b
) >> 1)
232 c
:= int(uint(start
+r
) >> 1)
233 if !data
.Less(p
-c
, c
) {
240 if start
< m
&& m
< end
{
241 rotate_func(data
, start
, m
, end
)
243 if a
< start
&& start
< mid
{
244 symMerge_func(data
, a
, start
, mid
)
246 if mid
< end
&& end
< b
{
247 symMerge_func(data
, mid
, end
, b
)
251 // Auto-generated variant of sort.go:rotate
252 func rotate_func(data lessSwap
, a
, m
, b
int) {
257 swapRange_func(data
, m
-i
, m
, j
)
260 swapRange_func(data
, m
-i
, m
+j
-i
, i
)
264 swapRange_func(data
, m
-i
, m
, i
)