blob: 51fa5032e9912a8d7db6005dd1d11291b422a312 [file] [log] [blame]
 // 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 sorts data[a:b] using insertion sort. func insertionSort(data Interface, a, b int) { for i := a + 1; i < b; i++ { for j := i; j > a && data.Less(j, j-1); j-- { data.Swap(j, j-1) } } } // siftDown implements the heap property on data[lo:hi]. // first is an offset into the array where the root of the heap lies. func siftDown(data Interface, lo, hi, first int) { root := lo for { child := 2*root + 1 if child >= hi { break } if child+1 < hi && data.Less(first+child, first+child+1) { child++ } if !data.Less(first+root, first+child) { return } data.Swap(first+root, first+child) root = child } } func heapSort(data Interface, a, b int) { first := a lo := 0 hi := b - a // Build heap with greatest element at top. for i := (hi - 1) / 2; i >= 0; i-- { siftDown(data, i, hi, first) } // Pop elements, largest first, into end of data. for i := hi - 1; i >= 0; i-- { data.Swap(first, first+i) siftDown(data, lo, i, first) } } // pdqsort 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(data Interface, a, b, limit int) { const maxInsertion = 12 var ( wasBalanced = true // whether the last partitioning was reasonably balanced wasPartitioned = true // whether the slice was already partitioned ) for { length := b - a if length <= maxInsertion { insertionSort(data, a, b) return } // Fall back to heapsort if too many bad choices were made. if limit == 0 { heapSort(data, a, b) return } // If the last partitioning was imbalanced, we need to breaking patterns. if !wasBalanced { breakPatterns(data, a, b) limit-- } pivot, hint := choosePivot(data, a, b) if hint == decreasingHint { reverseRange(data, a, b) // 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. pivot = (b - 1) - (pivot - a) hint = increasingHint } // The slice is likely already sorted. if wasBalanced && wasPartitioned && hint == increasingHint { if partialInsertionSort(data, a, b) { return } } // Probably the slice contains many duplicate elements, partition the slice into // elements equal to and elements greater than the pivot. if a > 0 && !data.Less(a-1, pivot) { mid := partitionEqual(data, a, b, pivot) a = mid continue } mid, alreadyPartitioned := partition(data, a, b, pivot) wasPartitioned = alreadyPartitioned leftLen, rightLen := mid-a, b-mid balanceThreshold := length / 8 if leftLen < rightLen { wasBalanced = leftLen >= balanceThreshold pdqsort(data, a, mid, limit) a = mid + 1 } else { wasBalanced = rightLen >= balanceThreshold pdqsort(data, mid+1, b, limit) b = mid } } } // partition does one quicksort partition. // Let p = data[pivot] // Moves elements in data[a:b] around, so that data[i]

=p for inewpivot. // On return, data[newpivot] = p func partition(data Interface, a, b, pivot int) (newpivot int, alreadyPartitioned bool) { data.Swap(a, pivot) i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned for i <= j && data.Less(i, a) { i++ } for i <= j && !data.Less(j, a) { j-- } if i > j { data.Swap(j, a) return j, true } data.Swap(i, j) i++ j-- for { for i <= j && data.Less(i, a) { i++ } for i <= j && !data.Less(j, a) { j-- } if i > j { break } data.Swap(i, j) i++ j-- } data.Swap(j, a) return j, false } // partitionEqual 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(data Interface, a, b, pivot int) (newpivot int) { data.Swap(a, pivot) i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned for { for i <= j && !data.Less(a, i) { i++ } for i <= j && data.Less(a, j) { j-- } if i > j { break } data.Swap(i, j) i++ j-- } return i } // partialInsertionSort partially sorts a slice, returns true if the slice is sorted at the end. func partialInsertionSort(data Interface, a, b int) bool { const ( maxSteps = 5 // maximum number of adjacent out-of-order pairs that will get shifted shortestShifting = 50 // don't shift any elements on short arrays ) i := a + 1 for j := 0; j < maxSteps; j++ { for i < b && !data.Less(i, i-1) { i++ } if i == b { return true } if b-a < shortestShifting { return false } data.Swap(i, i-1) // Shift the smaller one to the left. if i-a >= 2 { for j := i - 1; j >= 1; j-- { if !data.Less(j, j-1) { break } data.Swap(j, j-1) } } // Shift the greater one to the right. if b-i >= 2 { for j := i + 1; j < b; j++ { if !data.Less(j, j-1) { break } data.Swap(j, j-1) } } } return false } // breakPatterns scatters some elements around in an attempt to break some patterns // that might cause imbalanced partitions in quicksort. func breakPatterns(data Interface, a, b int) { length := b - a if length >= 8 { random := xorshift(length) modulus := nextPowerOfTwo(length) for idx := a + (length/4)*2 - 1; idx <= a+(length/4)*2+1; idx++ { other := int(uint(random.Next()) & (modulus - 1)) if other >= length { other -= length } data.Swap(idx, a+other) } } } // choosePivot 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(data Interface, a, b int) (pivot int, hint sortedHint) { const ( shortestNinther = 50 maxSwaps = 4 * 3 ) l := b - a var ( swaps int i = a + l/4*1 j = a + l/4*2 k = a + l/4*3 ) if l >= 8 { if l >= shortestNinther { // Tukey ninther method, the idea came from Rust's implementation. i = medianAdjacent(data, i, &swaps) j = medianAdjacent(data, j, &swaps) k = medianAdjacent(data, k, &swaps) } // Find the median among i, j, k and stores it into j. j = median(data, i, j, k, &swaps) } switch swaps { case 0: return j, increasingHint case maxSwaps: return j, decreasingHint default: return j, unknownHint } } // order2 returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a. func order2(data Interface, a, b int, swaps *int) (int, int) { if data.Less(b, a) { *swaps++ return b, a } return a, b } // median returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c. func median(data Interface, a, b, c int, swaps *int) int { a, b = order2(data, a, b, swaps) b, c = order2(data, b, c, swaps) a, b = order2(data, a, b, swaps) return b } // medianAdjacent finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a. func medianAdjacent(data Interface, a int, swaps *int) int { return median(data, a-1, a, a+1, swaps) } func reverseRange(data Interface, a, b int) { i := a j := b - 1 for i < j { data.Swap(i, j) i++ j-- } } func swapRange(data Interface, a, b, n int) { for i := 0; i < n; i++ { data.Swap(a+i, b+i) } } func stable(data Interface, n int) { blockSize := 20 // must be > 0 a, b := 0, blockSize for b <= n { insertionSort(data, a, b) a = b b += blockSize } insertionSort(data, a, n) for blockSize < n { a, b = 0, 2*blockSize for b <= n { symMerge(data, a, a+blockSize, b) a = b b += 2 * blockSize } if m := a + blockSize; m < n { symMerge(data, a, m, n) } blockSize *= 2 } } // symMerge 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(data Interface, a, m, b 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 m-a == 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. i := m j := b for i < j { h := int(uint(i+j) >> 1) if data.Less(h, a) { i = h + 1 } else { j = h } } // Swap values until data[a] reaches the position before i. for k := a; k < i-1; k++ { data.Swap(k, k+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 b-m == 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. i := a j := m for i < j { h := int(uint(i+j) >> 1) if !data.Less(m, h) { i = h + 1 } else { j = h } } // Swap values until data[m] reaches the position i. for k := m; k > i; k-- { data.Swap(k, k-1) } return } mid := int(uint(a+b) >> 1) n := mid + m var start, r int if m > mid { start = n - b r = mid } else { start = a r = m } p := n - 1 for start < r { c := int(uint(start+r) >> 1) if !data.Less(p-c, c) { start = c + 1 } else { r = c } } end := n - start if start < m && m < end { rotate(data, start, m, end) } if a < start && start < mid { symMerge(data, a, start, mid) } if mid < end && end < b { symMerge(data, mid, end, b) } } // rotate 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(data Interface, a, m, b int) { i := m - a j := b - m for i != j { if i > j { swapRange(data, m-i, m, j) i -= j } else { swapRange(data, m-i, m+j-i, i) j -= i } } // i == j swapRange(data, m-i, m, i) }