1 // Copyright 2022 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4 5 //go:build ignore
6 7 // This program is run via "go generate" (via a directive in sort.go)
8 // to generate implementation variants of the underlying sorting algorithm.
9 // When passed the -generic flag it generates generic variants of sorting;
10 // otherwise it generates the non-generic variants used by the sort package.
11 12 package main
13 14 import (
15 "bytes"
16 "flag"
17 "fmt"
18 "go/format"
19 "log"
20 "os"
21 "text/template"
22 )
23 24 type Variant struct {
25 // Name is the variant name: should be unique among variants.
26 Name []byte
27 28 // Path is the file path into which the generator will emit the code for this
29 // variant.
30 Path []byte
31 32 // Package is the package this code will be emitted into.
33 Package []byte
34 35 // Imports is the imports needed for this package.
36 Imports []byte
37 38 // FuncSuffix is appended to all function names in this variant's code. All
39 // suffixes should be unique within a package.
40 FuncSuffix []byte
41 42 // DataType is the type of the data parameter of functions in this variant's
43 // code.
44 DataType []byte
45 46 // TypeParam is the optional type parameter for the function.
47 TypeParam []byte
48 49 // ExtraParam is an extra parameter to pass to the function. Should begin with
50 // ", " to separate from other params.
51 ExtraParam []byte
52 53 // ExtraArg is an extra argument to pass to calls between functions; typically
54 // it invokes ExtraParam. Should begin with ", " to separate from other args.
55 ExtraArg []byte
56 57 // Funcs is a map of functions used from within the template. The following
58 // functions are expected to exist:
59 //
60 // Less (name, i, j):
61 // emits a comparison expression that checks if the value `name` at
62 // index `i` is smaller than at index `j`.
63 //
64 // Swap (name, i, j):
65 // emits a statement that performs a data swap between elements `i` and
66 // `j` of the value `name`.
67 Funcs template.FuncMap
68 }
69 70 var (
71 traditionalVariants = []Variant{
72 Variant{
73 Name: "interface",
74 Path: "zsortinterface.go",
75 Package: "sort",
76 Imports: "",
77 FuncSuffix: "",
78 TypeParam: "",
79 ExtraParam: "",
80 ExtraArg: "",
81 DataType: "Interface",
82 Funcs: template.FuncMap{
83 "Less": func(name, i, j []byte) []byte {
84 return fmt.Sprintf("%s.Less(%s, %s)", name, i, j)
85 },
86 "Swap": func(name, i, j []byte) []byte {
87 return fmt.Sprintf("%s.Swap(%s, %s)", name, i, j)
88 },
89 },
90 },
91 Variant{
92 Name: "func",
93 Path: "zsortfunc.go",
94 Package: "sort",
95 Imports: "",
96 FuncSuffix: "_func",
97 TypeParam: "",
98 ExtraParam: "",
99 ExtraArg: "",
100 DataType: "lessSwap",
101 Funcs: template.FuncMap{
102 "Less": func(name, i, j []byte) []byte {
103 return fmt.Sprintf("%s.Less(%s, %s)", name, i, j)
104 },
105 "Swap": func(name, i, j []byte) []byte {
106 return fmt.Sprintf("%s.Swap(%s, %s)", name, i, j)
107 },
108 },
109 },
110 }
111 112 genericVariants = []Variant{
113 Variant{
114 Name: "generic_ordered",
115 Path: "zsortordered.go",
116 Package: "slices",
117 Imports: "import \"cmp\"\n",
118 FuncSuffix: "Ordered",
119 TypeParam: "[E cmp.Ordered]",
120 ExtraParam: "",
121 ExtraArg: "",
122 DataType: "[]E",
123 Funcs: template.FuncMap{
124 "Less": func(name, i, j []byte) []byte {
125 return fmt.Sprintf("cmp.Less(%s[%s], %s[%s])", name, i, name, j)
126 },
127 "Swap": func(name, i, j []byte) []byte {
128 return fmt.Sprintf("%s[%s], %s[%s] = %s[%s], %s[%s]", name, i, name, j, name, j, name, i)
129 },
130 },
131 },
132 Variant{
133 Name: "generic_func",
134 Path: "zsortanyfunc.go",
135 Package: "slices",
136 FuncSuffix: "CmpFunc",
137 TypeParam: "[E any]",
138 ExtraParam: ", cmp func(a, b E) int",
139 ExtraArg: ", cmp",
140 DataType: "[]E",
141 Funcs: template.FuncMap{
142 "Less": func(name, i, j []byte) []byte {
143 return fmt.Sprintf("(cmp(%s[%s], %s[%s]) < 0)", name, i, name, j)
144 },
145 "Swap": func(name, i, j []byte) []byte {
146 return fmt.Sprintf("%s[%s], %s[%s] = %s[%s], %s[%s]", name, i, name, j, name, j, name, i)
147 },
148 },
149 },
150 }
151 152 expVariants = []Variant{
153 Variant{
154 Name: "exp_ordered",
155 Path: "zsortordered.go",
156 Package: "slices",
157 Imports: "import \"golang.org/x/exp/constraints\"\n",
158 FuncSuffix: "Ordered",
159 TypeParam: "[E constraints.Ordered]",
160 ExtraParam: "",
161 ExtraArg: "",
162 DataType: "[]E",
163 Funcs: template.FuncMap{
164 "Less": func(name, i, j []byte) []byte {
165 return fmt.Sprintf("cmpLess(%s[%s], %s[%s])", name, i, name, j)
166 },
167 "Swap": func(name, i, j []byte) []byte {
168 return fmt.Sprintf("%s[%s], %s[%s] = %s[%s], %s[%s]", name, i, name, j, name, j, name, i)
169 },
170 },
171 },
172 Variant{
173 Name: "exp_func",
174 Path: "zsortanyfunc.go",
175 Package: "slices",
176 FuncSuffix: "CmpFunc",
177 TypeParam: "[E any]",
178 ExtraParam: ", cmp func(a, b E) int",
179 ExtraArg: ", cmp",
180 DataType: "[]E",
181 Funcs: template.FuncMap{
182 "Less": func(name, i, j []byte) []byte {
183 return fmt.Sprintf("(cmp(%s[%s], %s[%s]) < 0)", name, i, name, j)
184 },
185 "Swap": func(name, i, j []byte) []byte {
186 return fmt.Sprintf("%s[%s], %s[%s] = %s[%s], %s[%s]", name, i, name, j, name, j, name, i)
187 },
188 },
189 },
190 }
191 )
192 193 func main() {
194 genGeneric := flag.Bool("generic", false, "generate generic versions")
195 genExp := flag.Bool("exp", false, "generate x/exp/slices versions")
196 flag.Parse()
197 198 var variants []Variant
199 if *genExp {
200 variants = expVariants
201 } else if *genGeneric {
202 variants = genericVariants
203 } else {
204 variants = traditionalVariants
205 }
206 for i := range variants {
207 generate(&variants[i])
208 }
209 }
210 211 // generate generates the code for variant `v` into a file named by `v.Path`.
212 func generate(v *Variant) {
213 // Parse templateCode anew for each variant because Parse requires Funcs to be
214 // registered, and it helps type-check the funcs.
215 tmpl, err := template.New("gen").Funcs(v.Funcs).Parse(templateCode)
216 if err != nil {
217 log.Fatal("template Parse:", err)
218 }
219 220 var out bytes.Buffer
221 err = tmpl.Execute(&out, v)
222 if err != nil {
223 log.Fatal("template Execute:", err)
224 }
225 226 formatted, err := format.Source(out.Bytes())
227 if err != nil {
228 log.Fatal("format:", err)
229 }
230 231 if err := os.WriteFile(v.Path, formatted, 0644); err != nil {
232 log.Fatal("WriteFile:", err)
233 }
234 }
235 236 var templateCode = `// Code generated by gen_sort_variants.go; DO NOT EDIT.
237 238 // Copyright 2022 The Go Authors. All rights reserved.
239 // Use of this source code is governed by a BSD-style
240 // license that can be found in the LICENSE file.
241 242 package {{.Package}}
243 244 {{.Imports}}
245 246 // insertionSort{{.FuncSuffix}} sorts data[a:b] using insertion sort.
247 func insertionSort{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b int {{.ExtraParam}}) {
248 for i := a + 1; i < b; i++ {
249 for j := i; j > a && {{Less "data" "j" "j-1"}}; j-- {
250 {{Swap "data" "j" "j-1"}}
251 }
252 }
253 }
254 255 // siftDown{{.FuncSuffix}} implements the heap property on data[lo:hi].
256 // first is an offset into the array where the root of the heap lies.
257 func siftDown{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, lo, hi, first int {{.ExtraParam}}) {
258 root := lo
259 for {
260 child := 2*root + 1
261 if child >= hi {
262 break
263 }
264 if child+1 < hi && {{Less "data" "first+child" "first+child+1"}} {
265 child++
266 }
267 if !{{Less "data" "first+root" "first+child"}} {
268 return
269 }
270 {{Swap "data" "first+root" "first+child"}}
271 root = child
272 }
273 }
274 275 func heapSort{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b int {{.ExtraParam}}) {
276 first := a
277 lo := 0
278 hi := b - a
279 280 // Build heap with greatest element at top.
281 for i := (hi - 1) / 2; i >= 0; i-- {
282 siftDown{{.FuncSuffix}}(data, i, hi, first {{.ExtraArg}})
283 }
284 285 // Pop elements, largest first, into end of data.
286 for i := hi - 1; i >= 0; i-- {
287 {{Swap "data" "first" "first+i"}}
288 siftDown{{.FuncSuffix}}(data, lo, i, first {{.ExtraArg}})
289 }
290 }
291 292 // pdqsort{{.FuncSuffix}} sorts data[a:b].
293 // The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort.
294 // pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf
295 // C++ implementation: https://github.com/orlp/pdqsort
296 // Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/
297 // limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.
298 func pdqsort{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b, limit int {{.ExtraParam}}) {
299 const maxInsertion = 12
300 301 var (
302 wasBalanced = true // whether the last partitioning was reasonably balanced
303 wasPartitioned = true // whether the slice was already partitioned
304 )
305 306 for {
307 length := b - a
308 309 if length <= maxInsertion {
310 insertionSort{{.FuncSuffix}}(data, a, b {{.ExtraArg}})
311 return
312 }
313 314 // Fall back to heapsort if too many bad choices were made.
315 if limit == 0 {
316 heapSort{{.FuncSuffix}}(data, a, b {{.ExtraArg}})
317 return
318 }
319 320 // If the last partitioning was imbalanced, we need to breaking patterns.
321 if !wasBalanced {
322 breakPatterns{{.FuncSuffix}}(data, a, b {{.ExtraArg}})
323 limit--
324 }
325 326 pivot, hint := choosePivot{{.FuncSuffix}}(data, a, b {{.ExtraArg}})
327 if hint == decreasingHint {
328 reverseRange{{.FuncSuffix}}(data, a, b {{.ExtraArg}})
329 // The chosen pivot was pivot-a elements after the start of the array.
330 // After reversing it is pivot-a elements before the end of the array.
331 // The idea came from Rust's implementation.
332 pivot = (b - 1) - (pivot - a)
333 hint = increasingHint
334 }
335 336 // The slice is likely already sorted.
337 if wasBalanced && wasPartitioned && hint == increasingHint {
338 if partialInsertionSort{{.FuncSuffix}}(data, a, b {{.ExtraArg}}) {
339 return
340 }
341 }
342 343 // Probably the slice contains many duplicate elements, partition the slice into
344 // elements equal to and elements greater than the pivot.
345 if a > 0 && !{{Less "data" "a-1" "pivot"}} {
346 mid := partitionEqual{{.FuncSuffix}}(data, a, b, pivot {{.ExtraArg}})
347 a = mid
348 continue
349 }
350 351 mid, alreadyPartitioned := partition{{.FuncSuffix}}(data, a, b, pivot {{.ExtraArg}})
352 wasPartitioned = alreadyPartitioned
353 354 leftLen, rightLen := mid-a, b-mid
355 balanceThreshold := length / 8
356 if leftLen < rightLen {
357 wasBalanced = leftLen >= balanceThreshold
358 pdqsort{{.FuncSuffix}}(data, a, mid, limit {{.ExtraArg}})
359 a = mid + 1
360 } else {
361 wasBalanced = rightLen >= balanceThreshold
362 pdqsort{{.FuncSuffix}}(data, mid+1, b, limit {{.ExtraArg}})
363 b = mid
364 }
365 }
366 }
367 368 // partition{{.FuncSuffix}} does one quicksort partition.
369 // Let p = data[pivot]
370 // Moves elements in data[a:b] around, so that data[i]<p and data[j]>=p for i<newpivot and j>newpivot.
371 // On return, data[newpivot] = p
372 func partition{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b, pivot int {{.ExtraParam}}) (newpivot int, alreadyPartitioned bool) {
373 {{Swap "data" "a" "pivot"}}
374 i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned
375 376 for i <= j && {{Less "data" "i" "a"}} {
377 i++
378 }
379 for i <= j && !{{Less "data" "j" "a"}} {
380 j--
381 }
382 if i > j {
383 {{Swap "data" "j" "a"}}
384 return j, true
385 }
386 {{Swap "data" "i" "j"}}
387 i++
388 j--
389 390 for {
391 for i <= j && {{Less "data" "i" "a"}} {
392 i++
393 }
394 for i <= j && !{{Less "data" "j" "a"}} {
395 j--
396 }
397 if i > j {
398 break
399 }
400 {{Swap "data" "i" "j"}}
401 i++
402 j--
403 }
404 {{Swap "data" "j" "a"}}
405 return j, false
406 }
407 408 // partitionEqual{{.FuncSuffix}} partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot].
409 // It assumed that data[a:b] does not contain elements smaller than the data[pivot].
410 func partitionEqual{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b, pivot int {{.ExtraParam}}) (newpivot int) {
411 {{Swap "data" "a" "pivot"}}
412 i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned
413 414 for {
415 for i <= j && !{{Less "data" "a" "i"}} {
416 i++
417 }
418 for i <= j && {{Less "data" "a" "j"}} {
419 j--
420 }
421 if i > j {
422 break
423 }
424 {{Swap "data" "i" "j"}}
425 i++
426 j--
427 }
428 return i
429 }
430 431 // partialInsertionSort{{.FuncSuffix}} partially sorts a slice, returns true if the slice is sorted at the end.
432 func partialInsertionSort{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b int {{.ExtraParam}}) bool {
433 const (
434 maxSteps = 5 // maximum number of adjacent out-of-order pairs that will get shifted
435 shortestShifting = 50 // don't shift any elements on short arrays
436 )
437 i := a + 1
438 for j := 0; j < maxSteps; j++ {
439 for i < b && !{{Less "data" "i" "i-1"}} {
440 i++
441 }
442 443 if i == b {
444 return true
445 }
446 447 if b-a < shortestShifting {
448 return false
449 }
450 451 {{Swap "data" "i" "i-1"}}
452 453 // Shift the smaller one to the left.
454 if i-a >= 2 {
455 for j := i - 1; j >= 1; j-- {
456 if !{{Less "data" "j" "j-1"}} {
457 break
458 }
459 {{Swap "data" "j" "j-1"}}
460 }
461 }
462 // Shift the greater one to the right.
463 if b-i >= 2 {
464 for j := i + 1; j < b; j++ {
465 if !{{Less "data" "j" "j-1"}} {
466 break
467 }
468 {{Swap "data" "j" "j-1"}}
469 }
470 }
471 }
472 return false
473 }
474 475 // breakPatterns{{.FuncSuffix}} scatters some elements around in an attempt to break some patterns
476 // that might cause imbalanced partitions in quicksort.
477 func breakPatterns{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b int {{.ExtraParam}}) {
478 length := b - a
479 if length >= 8 {
480 random := xorshift(length)
481 modulus := nextPowerOfTwo(length)
482 483 for idx := a + (length/4)*2 - 1; idx <= a + (length/4)*2 + 1; idx++ {
484 other := int(uint(random.Next()) & (modulus - 1))
485 if other >= length {
486 other -= length
487 }
488 {{Swap "data" "idx" "a+other"}}
489 }
490 }
491 }
492 493 // choosePivot{{.FuncSuffix}} chooses a pivot in data[a:b].
494 //
495 // [0,8): chooses a static pivot.
496 // [8,shortestNinther): uses the simple median-of-three method.
497 // [shortestNinther,∞): uses the Tukey ninther method.
498 func choosePivot{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b int {{.ExtraParam}}) (pivot int, hint sortedHint) {
499 const (
500 shortestNinther = 50
501 maxSwaps = 4 * 3
502 )
503 504 l := b - a
505 506 var (
507 swaps int
508 i = a + l/4*1
509 j = a + l/4*2
510 k = a + l/4*3
511 )
512 513 if l >= 8 {
514 if l >= shortestNinther {
515 // Tukey ninther method, the idea came from Rust's implementation.
516 i = medianAdjacent{{.FuncSuffix}}(data, i, &swaps {{.ExtraArg}})
517 j = medianAdjacent{{.FuncSuffix}}(data, j, &swaps {{.ExtraArg}})
518 k = medianAdjacent{{.FuncSuffix}}(data, k, &swaps {{.ExtraArg}})
519 }
520 // Find the median among i, j, k and stores it into j.
521 j = median{{.FuncSuffix}}(data, i, j, k, &swaps {{.ExtraArg}})
522 }
523 524 switch swaps {
525 case 0:
526 return j, increasingHint
527 case maxSwaps:
528 return j, decreasingHint
529 default:
530 return j, unknownHint
531 }
532 }
533 534 // order2{{.FuncSuffix}} returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.
535 func order2{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b int, swaps *int {{.ExtraParam}}) (int, int) {
536 if {{Less "data" "b" "a"}} {
537 *swaps++
538 return b, a
539 }
540 return a, b
541 }
542 543 // median{{.FuncSuffix}} returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.
544 func median{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b, c int, swaps *int {{.ExtraParam}}) int {
545 a, b = order2{{.FuncSuffix}}(data, a, b, swaps {{.ExtraArg}})
546 b, c = order2{{.FuncSuffix}}(data, b, c, swaps {{.ExtraArg}})
547 a, b = order2{{.FuncSuffix}}(data, a, b, swaps {{.ExtraArg}})
548 return b
549 }
550 551 // medianAdjacent{{.FuncSuffix}} finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.
552 func medianAdjacent{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a int, swaps *int {{.ExtraParam}}) int {
553 return median{{.FuncSuffix}}(data, a-1, a, a+1, swaps {{.ExtraArg}})
554 }
555 556 func reverseRange{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b int {{.ExtraParam}}) {
557 i := a
558 j := b - 1
559 for i < j {
560 {{Swap "data" "i" "j"}}
561 i++
562 j--
563 }
564 }
565 566 func swapRange{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, b, n int {{.ExtraParam}}) {
567 for i := 0; i < n; i++ {
568 {{Swap "data" "a+i" "b+i"}}
569 }
570 }
571 572 func stable{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, n int {{.ExtraParam}}) {
573 blockSize := 20 // must be > 0
574 a, b := 0, blockSize
575 for b <= n {
576 insertionSort{{.FuncSuffix}}(data, a, b {{.ExtraArg}})
577 a = b
578 b += blockSize
579 }
580 insertionSort{{.FuncSuffix}}(data, a, n {{.ExtraArg}})
581 582 for blockSize < n {
583 a, b = 0, 2*blockSize
584 for b <= n {
585 symMerge{{.FuncSuffix}}(data, a, a+blockSize, b {{.ExtraArg}})
586 a = b
587 b += 2 * blockSize
588 }
589 if m := a + blockSize; m < n {
590 symMerge{{.FuncSuffix}}(data, a, m, n {{.ExtraArg}})
591 }
592 blockSize *= 2
593 }
594 }
595 596 // symMerge{{.FuncSuffix}} merges the two sorted subsequences data[a:m] and data[m:b] using
597 // the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
598 // Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
599 // Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
600 // Computer Science, pages 714-723. Springer, 2004.
601 //
602 // Let M = m-a and N = b-n. Wolog M < N.
603 // The recursion depth is bound by ceil(log(N+M)).
604 // The algorithm needs O(M*log(N/M + 1)) calls to data.Less.
605 // The algorithm needs O((M+N)*log(M)) calls to data.Swap.
606 //
607 // The paper gives O((M+N)*log(M)) as the number of assignments assuming a
608 // rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation
609 // in the paper carries through for Swap operations, especially as the block
610 // swapping rotate uses only O(M+N) Swaps.
611 //
612 // symMerge assumes non-degenerate arguments: a < m && m < b.
613 // Having the caller check this condition eliminates many leaf recursion calls,
614 // which improves performance.
615 func symMerge{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, m, b int {{.ExtraParam}}) {
616 // Avoid unnecessary recursions of symMerge
617 // by direct insertion of data[a] into data[m:b]
618 // if data[a:m] only contains one element.
619 if m-a == 1 {
620 // Use binary search to find the lowest index i
621 // such that data[i] >= data[a] for m <= i < b.
622 // Exit the search loop with i == b in case no such index exists.
623 i := m
624 j := b
625 for i < j {
626 h := int(uint(i+j) >> 1)
627 if {{Less "data" "h" "a"}} {
628 i = h + 1
629 } else {
630 j = h
631 }
632 }
633 // Swap values until data[a] reaches the position before i.
634 for k := a; k < i-1; k++ {
635 {{Swap "data" "k" "k+1"}}
636 }
637 return
638 }
639 640 // Avoid unnecessary recursions of symMerge
641 // by direct insertion of data[m] into data[a:m]
642 // if data[m:b] only contains one element.
643 if b-m == 1 {
644 // Use binary search to find the lowest index i
645 // such that data[i] > data[m] for a <= i < m.
646 // Exit the search loop with i == m in case no such index exists.
647 i := a
648 j := m
649 for i < j {
650 h := int(uint(i+j) >> 1)
651 if !{{Less "data" "m" "h"}} {
652 i = h + 1
653 } else {
654 j = h
655 }
656 }
657 // Swap values until data[m] reaches the position i.
658 for k := m; k > i; k-- {
659 {{Swap "data" "k" "k-1"}}
660 }
661 return
662 }
663 664 mid := int(uint(a+b) >> 1)
665 n := mid + m
666 var start, r int
667 if m > mid {
668 start = n - b
669 r = mid
670 } else {
671 start = a
672 r = m
673 }
674 p := n - 1
675 676 for start < r {
677 c := int(uint(start+r) >> 1)
678 if !{{Less "data" "p-c" "c"}} {
679 start = c + 1
680 } else {
681 r = c
682 }
683 }
684 685 end := n - start
686 if start < m && m < end {
687 rotate{{.FuncSuffix}}(data, start, m, end {{.ExtraArg}})
688 }
689 if a < start && start < mid {
690 symMerge{{.FuncSuffix}}(data, a, start, mid {{.ExtraArg}})
691 }
692 if mid < end && end < b {
693 symMerge{{.FuncSuffix}}(data, mid, end, b {{.ExtraArg}})
694 }
695 }
696 697 // rotate{{.FuncSuffix}} rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data:
698 // Data of the form 'x u v y' is changed to 'x v u y'.
699 // rotate performs at most b-a many calls to data.Swap,
700 // and it assumes non-degenerate arguments: a < m && m < b.
701 func rotate{{.FuncSuffix}}{{.TypeParam}}(data {{.DataType}}, a, m, b int {{.ExtraParam}}) {
702 i := m - a
703 j := b - m
704 705 for i != j {
706 if i > j {
707 swapRange{{.FuncSuffix}}(data, m-i, m, j {{.ExtraArg}})
708 i -= j
709 } else {
710 swapRange{{.FuncSuffix}}(data, m-i, m+j-i, i {{.ExtraArg}})
711 j -= i
712 }
713 }
714 // i == j
715 swapRange{{.FuncSuffix}}(data, m-i, m, i {{.ExtraArg}})
716 }
717 `
718