// Code generated by gen_sort_variants.go; DO NOT EDIT.// Copyright 2022 The Go Authors. All rights reserved.// Use of this source code is governed by a BSD-style// license that can be found in the LICENSE file.package sort// insertionSort_func sorts data[a:b] using insertion sort.func insertionSort_func( lessSwap, , int) {for := + 1; < ; ++ {for := ; > && .Less(, -1); -- { .Swap(, -1) } }}// siftDown_func implements the heap property on data[lo:hi].// first is an offset into the array where the root of the heap lies.func siftDown_func( lessSwap, , , int) { := for { := 2* + 1if >= {break }if +1 < && .Less(+, ++1) { ++ }if !.Less(+, +) {return } .Swap(+, +) = }}func heapSort_func( lessSwap, , int) { := := 0 := - // Build heap with greatest element at top.for := ( - 1) / 2; >= 0; -- {siftDown_func(, , , ) }// Pop elements, largest first, into end of data.for := - 1; >= 0; -- { .Swap(, +)siftDown_func(, , , ) }}// pdqsort_func sorts data[a:b].// The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort.// pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf// C++ implementation: https://github.com/orlp/pdqsort// Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/// limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.func pdqsort_func( lessSwap, , , int) {const = 12var ( = true// whether the last partitioning was reasonably balanced = true// whether the slice was already partitioned )for { := - if <= {insertionSort_func(, , )return }// Fall back to heapsort if too many bad choices were made.if == 0 {heapSort_func(, , )return }// If the last partitioning was imbalanced, we need to breaking patterns.if ! {breakPatterns_func(, , ) -- } , := choosePivot_func(, , )if == decreasingHint {reverseRange_func(, , )// The chosen pivot was pivot-a elements after the start of the array. // After reversing it is pivot-a elements before the end of the array. // The idea came from Rust's implementation. = ( - 1) - ( - ) = increasingHint }// The slice is likely already sorted.if && && == increasingHint {ifpartialInsertionSort_func(, , ) {return } }// Probably the slice contains many duplicate elements, partition the slice into // elements equal to and elements greater than the pivot.if > 0 && !.Less(-1, ) { := partitionEqual_func(, , , ) = continue } , := partition_func(, , , ) = , := -, - := / 8if < { = >= (, , , ) = + 1 } else { = >= (, +1, , ) = } }}// partition_func does one quicksort partition.// Let p = data[pivot]// Moves elements in data[a:b] around, so that data[i]<p and data[j]>=p for i<newpivot and j>newpivot.// On return, data[newpivot] = pfunc partition_func( lessSwap, , , int) ( int, bool) { .Swap(, ) , := +1, -1// i and j are inclusive of the elements remaining to be partitionedfor <= && .Less(, ) { ++ }for <= && !.Less(, ) { -- }if > { .Swap(, )return , true } .Swap(, ) ++ --for {for <= && .Less(, ) { ++ }for <= && !.Less(, ) { -- }if > {break } .Swap(, ) ++ -- } .Swap(, )return , false}// partitionEqual_func partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot].// It assumed that data[a:b] does not contain elements smaller than the data[pivot].func partitionEqual_func( lessSwap, , , int) ( int) { .Swap(, ) , := +1, -1// i and j are inclusive of the elements remaining to be partitionedfor {for <= && !.Less(, ) { ++ }for <= && .Less(, ) { -- }if > {break } .Swap(, ) ++ -- }return}// partialInsertionSort_func partially sorts a slice, returns true if the slice is sorted at the end.func partialInsertionSort_func( lessSwap, , int) bool {const ( = 5// maximum number of adjacent out-of-order pairs that will get shifted = 50// don't shift any elements on short arrays ) := + 1for := 0; < ; ++ {for < && !.Less(, -1) { ++ }if == {returntrue }if - < {returnfalse } .Swap(, -1)// Shift the smaller one to the left.if - >= 2 {for := - 1; >= 1; -- {if !.Less(, -1) {break } .Swap(, -1) } }// Shift the greater one to the right.if - >= 2 {for := + 1; < ; ++ {if !.Less(, -1) {break } .Swap(, -1) } } }returnfalse}// breakPatterns_func scatters some elements around in an attempt to break some patterns// that might cause imbalanced partitions in quicksort.func breakPatterns_func( lessSwap, , int) { := - if >= 8 { := xorshift() := nextPowerOfTwo()for := + (/4)*2 - 1; <= +(/4)*2+1; ++ { := int(uint(.Next()) & ( - 1))if >= { -= } .Swap(, +) } }}// choosePivot_func chooses a pivot in data[a:b].//// [0,8): chooses a static pivot.// [8,shortestNinther): uses the simple median-of-three method.// [shortestNinther,∞): uses the Tukey ninther method.func choosePivot_func( lessSwap, , int) ( int, sortedHint) {const ( = 50 = 4 * 3 ) := - var (int = + /4*1 = + /4*2 = + /4*3 )if >= 8 {if >= {// Tukey ninther method, the idea came from Rust's implementation. = medianAdjacent_func(, , &) = medianAdjacent_func(, , &) = medianAdjacent_func(, , &) }// Find the median among i, j, k and stores it into j. = median_func(, , , , &) }switch {case0:return , increasingHintcase :return , decreasingHintdefault:return , unknownHint }}// order2_func returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.func order2_func( lessSwap, , int, *int) (int, int) {if .Less(, ) { *++return , }return , }// median_func returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.func median_func( lessSwap, , , int, *int) int { , = order2_func(, , , ) , = order2_func(, , , ) , = order2_func(, , , )return}// medianAdjacent_func finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.func medianAdjacent_func( lessSwap, int, *int) int {returnmedian_func(, -1, , +1, )}func reverseRange_func( lessSwap, , int) { := := - 1for < { .Swap(, ) ++ -- }}func swapRange_func( lessSwap, , , int) {for := 0; < ; ++ { .Swap(+, +) }}func stable_func( lessSwap, int) { := 20// must be > 0 , := 0, for <= {insertionSort_func(, , ) = += }insertionSort_func(, , )for < { , = 0, 2*for <= {symMerge_func(, , +, ) = += 2 * }if := + ; < {symMerge_func(, , , ) } *= 2 }}// symMerge_func merges the two sorted subsequences data[a:m] and data[m:b] using// the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum// Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz// Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in// Computer Science, pages 714-723. Springer, 2004.//// Let M = m-a and N = b-n. Wolog M < N.// The recursion depth is bound by ceil(log(N+M)).// The algorithm needs O(M*log(N/M + 1)) calls to data.Less.// The algorithm needs O((M+N)*log(M)) calls to data.Swap.//// The paper gives O((M+N)*log(M)) as the number of assignments assuming a// rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation// in the paper carries through for Swap operations, especially as the block// swapping rotate uses only O(M+N) Swaps.//// symMerge assumes non-degenerate arguments: a < m && m < b.// Having the caller check this condition eliminates many leaf recursion calls,// which improves performance.func symMerge_func( lessSwap, , , int) {// Avoid unnecessary recursions of symMerge // by direct insertion of data[a] into data[m:b] // if data[a:m] only contains one element.if - == 1 {// Use binary search to find the lowest index i // such that data[i] >= data[a] for m <= i < b. // Exit the search loop with i == b in case no such index exists. := := for < { := int(uint(+) >> 1)if .Less(, ) { = + 1 } else { = } }// Swap values until data[a] reaches the position before i.for := ; < -1; ++ { .Swap(, +1) }return }// Avoid unnecessary recursions of symMerge // by direct insertion of data[m] into data[a:m] // if data[m:b] only contains one element.if - == 1 {// Use binary search to find the lowest index i // such that data[i] > data[m] for a <= i < m. // Exit the search loop with i == m in case no such index exists. := := for < { := int(uint(+) >> 1)if !.Less(, ) { = + 1 } else { = } }// Swap values until data[m] reaches the position i.for := ; > ; -- { .Swap(, -1) }return } := int(uint(+) >> 1) := + var , intif > { = - = } else { = = } := - 1for < { := int(uint(+) >> 1)if !.Less(-, ) { = + 1 } else { = } } := - if < && < {rotate_func(, , , ) }if < && < { (, , , ) }if < && < { (, , , ) }}// rotate_func rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data:// Data of the form 'x u v y' is changed to 'x v u y'.// rotate performs at most b-a many calls to data.Swap,// and it assumes non-degenerate arguments: a < m && m < b.func rotate_func( lessSwap, , , int) { := - := - for != {if > {swapRange_func(, -, , ) -= } else {swapRange_func(, -, +-, ) -= } }// i == jswapRange_func(, -, , )}
The pages are generated with Goldsv0.7.3-preview. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @zigo_101 (reachable from the left QR code) to get the latest news of Golds.