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 12package main 13 14import ( 15 "bytes" 16 "flag" 17 "fmt" 18 "go/format" 19 "log" 20 "os" 21 "text/template" 22) 23 24type Variant struct { 25 // Name is the variant name: should be unique among variants. 26 Name string 27 28 // Path is the file path into which the generator will emit the code for this 29 // variant. 30 Path string 31 32 // Package is the package this code will be emitted into. 33 Package string 34 35 // Imports is the imports needed for this package. 36 Imports string 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 string 41 42 // DataType is the type of the data parameter of functions in this variant's 43 // code. 44 DataType string 45 46 // TypeParam is the optional type parameter for the function. 47 TypeParam string 48 49 // ExtraParam is an extra parameter to pass to the function. Should begin with 50 // ", " to separate from other params. 51 ExtraParam string 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 string 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 70var ( 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 string) string { 84 return fmt.Sprintf("%s.Less(%s, %s)", name, i, j) 85 }, 86 "Swap": func(name, i, j string) string { 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 string) string { 103 return fmt.Sprintf("%s.Less(%s, %s)", name, i, j) 104 }, 105 "Swap": func(name, i, j string) string { 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 string) string { 125 return fmt.Sprintf("cmp.Less(%s[%s], %s[%s])", name, i, name, j) 126 }, 127 "Swap": func(name, i, j string) string { 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 string) string { 143 return fmt.Sprintf("(cmp(%s[%s], %s[%s]) < 0)", name, i, name, j) 144 }, 145 "Swap": func(name, i, j string) string { 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 string) string { 165 return fmt.Sprintf("cmpLess(%s[%s], %s[%s])", name, i, name, j) 166 }, 167 "Swap": func(name, i, j string) string { 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 string) string { 183 return fmt.Sprintf("(cmp(%s[%s], %s[%s]) < 0)", name, i, name, j) 184 }, 185 "Swap": func(name, i, j string) string { 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 193func 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`. 212func 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 236var 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 242package {{.Package}} 243 244{{.Imports}} 245 246// insertionSort{{.FuncSuffix}} sorts data[a:b] using insertion sort. 247func 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. 257func 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 275func 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. 298func 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 372func 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]. 410func 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. 432func 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. 477func 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. 498func 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. 535func 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. 544func 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. 552func 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 556func 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 566func 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 572func 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. 615func 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. 701func 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